Mely n-ekre lehet n csúcsú,4-reguláris, egyszerű, síkba rajzolható gráfot konstruálni?

Nos, akkor megválaszolom az általam feltett kérdést :D

Szóval:

Ha 4-reguláris és egyszerű, akkor legalább 5 csúcsa van. Ha n=5, akkor ez csak az ötcsúcsú teljes gráf lehet, amiről tudjuk, hogy nem síkbarajzolható (lásd az első hozzászólást)

Tegyük fel hogy n>5 páros, legyen n=2k. Rajzoljunk egy k-hosszú kört, és a belsejébe is egy k-hosszú kört. Ebben a gráfban most minden csúcs foka kettő. Minden csúcsból húzzunk még két élet a másik kör két csúcsához, úgy, hogy ezek a két kör között haladó élek összességében egy cikk-cakkos körvonalat adjanak ki. Ezzel megoldottuk a feladatot az ötnél nagyobb páros számokra.

Tegyük fel, hogy van egy, a feltételeknek megfelelő n-csúcsú gráfunk, és van benne háromszög. Ekkor tudunk csinálni n+3 csúcsú, a feltételeknek megfelelő gráfot úgy, hogy veszünk egy háromszöget, mindhárom élét megtörjük egy új csúccsal, és ezeket a csúcsokat összekötjük egymással (tulajdonképpen behúztuk a háromszög középvonalait). Minden, az előző szakaszban konstruált páros csúcsszámú gráfban van háromszög (a két kezdeti körvonal között csak háromszögek vannak), tehát ha n>=9 páratlan, akkor is tudunk konstruálni ilyen n-csúcsú gráfot.

Egyetlen fekete bárány maradt: n=7. Erre kézzel-lábbal, próbálgatással be lehet bizonyítani, hogy nem megy. Inkább rajzolni kéne hozzá, mint magyarázni, ezért ezt az olvasóra bízom :D

De adok tippet: Az Euler-egyenlet felhasználásával belátható, hogy ha van jó 7-csúcsú gráf, akkor abban pontosan egy négyszög van, a többi oldal pedig háromszög kell legyen. Ennek az ismeretnek a birtokában kezdjetek el rajzolgatni.