matma
KLAUDIA: Proszę o sprawdzenie:
Pokaż, że jeśli graf jest prosty i stopnień każdego wierzchołka jest większy od n2 , to
graf jest spójny.
ROZWIĄZANIE:
1. Dla 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.
2. Dla n = 2k+1
Wybieramy wierzchołek stopnia k+2
Wybieramy drugi wierzcholek stopnia (2k+1)−(k+2)−1−1=k+1<k+2
Sprzeczność
