Feladat: 2.24.
Mutassuk meg, hogy a
2.23. feladatban használt gondolatmenet ,,egyirányú", az ottani b) állítás megfordítása nem igaz: abból, hogy egy
n elemű halmaznak megadható
n darab
k elemű részhalmaza úgy, hogy közülük bármely kettőnek legfeljebb egy közös eleme van, még nem következik, hogy van olyan
n pontú
k-reguláris gráf, amelyben nincs
C4
.
Megoldás: 2.24
Megmutatjuk a következőt: egy hételemű halmaznak megadható hét darab háromelemű részhalmaza úgy, hogy közülük bármely kettőnek pontosan egy közös eleme van. Ez jó ellenpéldának, hiszen hétpontú 3-reguláris gráf egyáltalán nincsen, mert a fokszámösszeg nem lehet páratlan.
A konstrukció: Legyen a
H halmaz hét eleme egy szabályos háromszög három csúcsa, három oldalfelező pontja és a háromszög súlypontja. A hét háromelemű halmaz: az egy oldalon levő pontok (három halmaz), a magasságokon levő pontok (három halmaz) és a beírt körön levő pontok (egy halmaz). E halmazok közül bármely kettőnek pontosan egy közös pontja van.