A H halmaz a nyolcpontú egyszerű gráfok halmaza. A következő állítás a H elemeire vonatkozik: Ha egy (nyolcpontú egyszerű) gráf minden pontjának fokszáma legalább 3, akkor a gráf összefüggő.

a) Döntse el, hogy az állítás igaz vagy hamis! Válaszát indokolja!

b) Fogalmazza meg az állítás megfordítását a H elemeire vonatkozóan, és döntse el a megfordított állításról, hogy igaz vagy hamis! Válaszát indokolja!

Az ABCDE konvex ötszög csúcsait piros, kék vagy zöld színűre színezzük úgy, hogy bármely két szomszédos csúcsa különböző színű legyen.

c) Hány különböző színezés lehetséges? (Az ötszög csúcsait megkülönböztetjük egymástól.)

Egy négypontú teljes gráf élei közül véletlenszerűen kiválasztott négy élt kiszínezünk zöldre. (Teljes gráf: olyan egyszerű gráf, melynek bármely két pontja között van él.)

d) Határozza meg annak a valószínűségét, hogy a zöldre színezett élek a gráf egy négypontú körének élei!

Megoldás:

a) hamis. Ellenpl. pl két négypontú teljes gráf egyesítése.

b) Ha egy (nyolcpontú egyszerű) gráf összefüggő, akkor a gráf minden pontjának fokszáma legalább 3. Hamis. Ellenpl.

c) 30

d) 0,2