Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?
A régi honlapot akarom!!! :-)

A B. 4899. feladat (2017. október)

B. 4899. A \(\displaystyle G\) egyszerű síkgráf minden csúcsa harmadfokú, és tudjuk, hogy létezik \(\displaystyle G\)-nek olyan síkba rajzolása, ahol \(\displaystyle G\) élei egymást nem metsző egységnyi hosszú szakaszok. Mutassuk meg, hogy \(\displaystyle G\)-nek legalább \(\displaystyle 8\) csúcsa van.

(5 pont)

A beküldési határidő 2017. november 10-én LEJÁRT.


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ó.


Statisztika:

A B. 4899. feladat értékelése még nem fejeződött be.


A KöMaL 2017. októberi matematika feladatai