Hogyan bizonyítjuk egy 9 csúcsú,28 élű gráfról, hogy összefüggő, és kromatikus száma legalább 3?

Gondolom a kromatikus szám bizonyítása valahogy úgy néz ki, hogy bizonyítjuk, hogy minden pont foka legalább 5 ( |V|/2-nél nagyobb ) kell legyen (kérdés hogyan?), aztán Dirac-tétele szerint ekkor van benne Hamilton kör, és mivel |V|=9, ezért ez a Hamilton-kör páratlan. Páratlan kör színezéséhez pedig legalább 3 szín szükséges.

Az összefüggőségre viszont semmi ötletem.

Végül is az összefüggőség bizonyítható úgy, hogy "legrosszabb esetben" van egy 8 pontú teljes gráfunk, 8*7/2 = 28 éllel, és egy izolált pontunk. Tehát a 9 pontú, 28 élű egyszerű gráf nem feltétlenül összefüggő.

A kromatikus számra viszont még nem sikerült rájönnöm továbbra sem.