Tekintsük a következő, egyszerű gráfokra vonatkozó állítást:

Ha a gráf minden pontjának fokszáma legalább 2, akkor a gráf biztosan összefüggő.

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

b) Fogalmazza meg az állítás megfordítását! Döntse el, hogy igaz vagy hamis az állítás megfordítása! Válaszát indokolja!

Tekintsük a következő halmazokat: $ P = \{\text{összefüggő gráfok}\} $, $ Q = \{\text{egyszerű gráfok}\} $, $ R = \{\text{kört tartalmazó gráfok}\} $.

c)Helyezze el az alábbi gráfok ábrájának sorszámát a fenti halmazábrában a megfelelő helyre!

d) Rajzoljon egy 6 pontú fagráfot az 5. ábrára, és helyezze el ennek a sorszámát is a fenti halmazábrában a megfelelő helyre!

Megoldás:

a) Az állítás hamis.

b) Az állítás megfordítása: Ha a gráf összefüggő, akkor minden pontjának fokszáma legalább 2. Az állítás hamis.

c)

d) Bármilyen jó 6 pontú fa. $ 5\in (P\cap Q)\setminus R $