matematykaszkolna.pl
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