A B. 4762. feladat (2016. január)

B. 4762. Egy egyszerű gráfnak minden csúcsa negyedfokú, és minden éléhez pontosan egy olyan csúcs található, amely az él mindkét végpontjával össze van kötve. Legalább hány csúcsa van egy ilyen gráfnak?

(3 pont)

A beküldési határidő 2016. február 10-én LEJÁRT.

Megoldás. Az alábbi ábrán kilenc csúcs esetére adunk egy konstrukciót:

Legyen most legfeljebb nyolc csúcsunk. Válasszunk ki kettőt (jelölje őket \(\displaystyle A\) és \(\displaystyle B\)), melyeket éllel összekötünk. Ezekhez egyértelműen tartozik egy harmadik (jelöljük \(\displaystyle C\)-vel), amivel mindkét csúcs össze van kötve. Mindhárom csúcs másodfokú lett, ezért még két élnek kell mindháromból indulnia – a feltevés szerint legfeljebb öt további csúcshoz. Ekkor viszont a skatulyaelv miatt lesz olyan csúcs, ami az \(\displaystyle A\), \(\displaystyle B\), és \(\displaystyle C\) pontok közül kettővel is össze van kötve. Következésképpen lesz olyan él, amihez több olyan csúcs is tartozik, ami mindkét végponttal össze van kötve. (Például ha a \(\displaystyle D\) csúcs az \(\displaystyle A\)-val és a \(\displaystyle C\)-vel is össze van kötve, akkor az \(\displaystyle AC\) élhez a \(\displaystyle B\) és a \(\displaystyle D\) csúcs is tartozik.) Ez ellentmond a feladat feltételének, így bebizonyítottuk, hogy kilencnél nem állhat kevesebb csúcsból a gráf.

Tehát a kérdéses gráfnak legalább kilenc csúcsa van.

Polgár Márton (Budapest, Németh László Gimn. 12. o. t.)

Statisztika:

123 dolgozat érkezett.
3 pontot kapott:	86 versenyző.
2 pontot kapott:	11 versenyző.
1 pontot kapott:	5 versenyző.
0 pontot kapott:	21 versenyző.

A KöMaL 2016. januári matematika feladatai