Bardzo proszę o pomoc w rozwiązaniu
Joanna: Udowodnij, że jeżeli graf prosty o n wierzchołkach ma więcej niż (n−1)(n−2)/2 krawędzi, to musi
być spójny.
4 cze 18:02
jc: Załóżmy, że mamy dwie części, po k i m wierzchołków, k+ m = n, k, m ≥ 1.
Taki graf ma co najwyżej [k(k−1) + m(m−1)]/2 ≤ (n−1)(n−2) /2 wierzchołków,
czyli graf który ma więcej niż (n−1)(n−2)/2 wierzchołków musi być spójny.
4 cze 18:46
kochanus_niepospolitus:
Niewprost.
Załóżmy, najbardziej 'radykalną' sytuację.
Jeden wierzchołek (nazwijmy go A) jest 'odizolowany' (nie ma żadnych krawędzi), a pozostałe
wierzchołki posiadają maksymalną możliwą ilość krawędzi.
Mamy n−1 wierzchołków z krawędziami. Policzmy ile tych krawędzi będzie:
n−2 + 0 | | (n−1)*(n−2) | |
| *(n−1) = |
| |
2 | | 2 | |
| (n−1)(n−2) | |
W zadaniu jest podane, że graf ma więcej niż |
| krawędzi, więc musi istnieć |
| 2 | |
przynajmniej jedna krawędź idąca do wierzchołka A.
Sprzeczność.
c.n.w.
4 cze 18:57
Joanna: Dziękuje bardzo
4 cze 19:44