Problem B. 4899. (October 2017)

B. 4899. The degree of each vertex of a simple planar graph \(\displaystyle G\) is 3, and \(\displaystyle G\) can be drawn in the plane with its edges represented by non-intersecting unit line segments. Show that \(\displaystyle G\) has at least \(\displaystyle 8\) vertices.

(5 pont)

Deadline expired on November 10, 2017.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Tudjuk, hogy a fokszámok összege az élek számának kétszerese, így mivel a gráf minden csúcsa harmadfokú, a csúcsok száma mindenképpen páros. Azt kell igazolni, hogy a gráfnak nem lehet 2, 4, vagy 6 csúcsa. Mivel minden él egy egységszakasz, ezért bármely két csúcs között legfeljebb 1 él lehet behúzva.

2 csúcs azért nem lehet, mert ekkor az élek száma maximum egy, viszont mindkét csúcsból legalább 3-nak kellene indulnia.

4 csúcs azért nem lehet, mert ekkor minden csúcsból minden csúcsba kellene élnek indulnia (azaz teljes lenne a gráf). Emiatt bármely három csúcsot kiválasztjuk, annak egy szabályos háromszöget kell alkotnia, ami csak akkor lehetséges, ha az egész egy tetraéder, ami egységszakasz élekkel nem síkba rajzolt.

Vizsgáljuk az \(\displaystyle n=6\) esetet. Ekkor a gráf komplementerében mindegyik pont foka 2. Ha a hatpontú egyszerű gráfnak mindegyik foka 2, akkor a gráf vagy két három élből álló kör, vagy egy darab hat élből álló kör.

Az első esetben az eredeti gráf pontjai két hármas csoportra oszthatók úgy, hogy csak a két csoport között vannak élek. Ez éppen a klasszikus "három ház - három kút" gráfot adja, amelyről tudjuk, hogy nem síkba rajzolható.

A második esetben legyenek a szomszédos csúcsok a komplementer gráfban rendre \(\displaystyle A\), \(\displaystyle B\), \(\displaystyle C\), \(\displaystyle D\), \(\displaystyle E\), \(\displaystyle F\). Az \(\displaystyle A\) csúcs szomszédai az eredeti gráfban pontosan \(\displaystyle C\), \(\displaystyle D\), \(\displaystyle E\). Igaz az összes további csúcsra is, hogy pontosan meg tudjuk mondani ebben a helyzetben a szomszédaikat. Figyelembe véve az eddigieket, ha létezik ilyen gráf, akkor az \(\displaystyle ADBE\), az \(\displaystyle ADFC\), továbbá az \(\displaystyle EBFC\) négyszög az élek keresztezése nélkül megrajzolható egységnyi oldalú rombuszok. Az \(\displaystyle ADBE\) és \(\displaystyle ADFC\) rombuszoknak egy éle közös, így csak úgy lehet a két rombuszt az élek keresztezése nélkül megrajzolni, ha az \(\displaystyle AD\) egyenes által meghatározott ellentétes félsíkban vannak. Tudjuk, hogy a \(\displaystyle CE\) és \(\displaystyle BF\) élek hossza is egység, az \(\displaystyle EBFC\) rombusz oldalalai is egység hosszúságúak. Az \(\displaystyle AD\) egység hosszúságú szakasz párhuzamos az \(\displaystyle EB\)-vel és a \(\displaystyle CF\)-fel. A párhuzamos, ugyanolyan hosszúságú \(\displaystyle AD\) vagy a \(\displaystyle CE\), vagy a \(\displaystyle BF\) szakaszt feltétlenül metszeni fogja.

A 6 csúcsú gráf tehát biztosan nem síkbarajzolható. Nem lehet a gráfnak 8-nál kevesebb csúcsa.

Az \(\displaystyle n=8\) esetre már adható konstrukció.

Statistics:

108 students sent a solution.
5 points:	Apagyi Dávid, Asztalos Ádám, Beke Csongor, Bukva Dávid, Busa 423 Máté, Csépányi István, Csertán András, Csiszár Zoltán, Csizmadia Viktória, Döbröntei Dávid Bence, Fülöp Anna Tácia, Füredi Erik Benjámin, Gáspár Attila, Hervay Bence, Horváth 721 Balázs, Janzer Orsolya Lili, Kántor András Imre, Kerekes Anna, Laki Anna, Martinák Zalán, Molnár Bálint, Molnár-Sáska Zoltán, Nagy Nándor, Noszály Áron, Perényi Gellért, Póta Balázs, Saár Patrik, Schifferer András, Schrettner Jakab, Szabó 417 Dávid, Szabó 997 Balázs István, Tiderenczl Dániel, Velkey Vince, Vida Tamás, Weisz Máté, Zsigri Bálint.
4 points:	42 students.
3 points:	12 students.
2 points:	16 students.
0 point:	2 students.

Problems in Mathematics of KöMaL, October 2017