Rozważ wszystkie możliwe grafy proste mające 200 wierzchołków.

[narusia]

(a) Wyjaśnij dlaczego każdy taki graf ma co najwyżej \({ 200 \choose 2} \)krawędzi.
(b) Wskaż wśród takich grafów ten, który ma \({ 199 \choose 2} \)krawędzi ale nie jest spójny.
(c) Udowodnij, że jeżeli graf z tej rodziny ma więcej niż \({ 199 \choose 2}\)krawędzi, to musi być spójny.

[kerajs]

a) Graf prosty nie ma pętli ani multikrawędzi. Najwięcej krawędzi wsród grafów prostych mających 200 wierzchołków ma klika o 200 wierzchołkach, i właśnie ona ma wskazaną liczbę krawędzi.

b) \(K_{199}\) i odizolowany wierzchołek.

c) Grafy niespójne mają najwięcej krawędzi gdy ich spójnymi podgrafami są kliki.
Liczba krawędzi jest największa gdy graf zawiera tylko dwa rozłączne podgrafy, a z tych najwięcej krawędzi ma graf wskazany w b)