Matma KLAUDIA: Pokaż, że jeśli graf jest prosty i stopnień każdego wierzchołka jest większy od ⁿ₂ , to graf jest spójny.

Blee: Niech n = 2k (parzysta liczba wierzcholkow) Wybieramy jeden wierzchołek, jest on stopnia minimum k+1 czyli laczy sie z minimum k+1 wierzcholkami Wybieramy drugi wierzcholek, jakiego moze byc stopnia aby nie laczyl sie z zadnym z wierzcholkow laczacych sie z pierwszym wierzcholkiem (oraz z nim samym)? Stopnia: 2k − (k+1) − 1 − 1 = k−3 < k+1 Sprzecznosc. Analogicznie dla n = 2k+1