Megadható-e a síkon 35 téglalap úgy, hogy mindegyik pontosan 5 vagy 7 másikat metsz?

Vegyünk egy gráfot, ahol a csúcsok szimbolizálják a téglalapokat, és két csúcs legyen összekötve, hogyha a csúcsok által jelölt téglalapok metszik egymást. Ebben az esetben lesz egy olyan gráfunk, ahol 35 csúcsunk van, a csúcsok fokszámai pedig vagy 5 vagy 7.

Mivel 35 darab páratlan számot adunk össze, ezért az összeg biztosan páratlan lesz, már pedig azt tudjuk, hogy szükséges (de nem elégséges) feltétel, hogy a fokszámok összege páros legyen, mivel fokszámösszeg/2=élszám, az élszámnak meg egésznek kell lennie.

Tehát nem adható meg 35 téglalap ilyen feltételekkel.

Gráfelmélet "legelsõ" tétele, hogy a fokszámok összege páros.

Ha van egy gráfelmélet témakörbe tartozó feladatod, és, minden szám páratlan benne, akkor érdemes lehet ezt használni.