Graf prosty
-
- Użytkownik
- Posty: 79
- Rejestracja: 27 maja 2007, o 11:46
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 14 razy
Graf prosty
Udowodnij, że jeżeli graf prosty o n wierzchołkach ma więcej niż (n-1)(n-2)/2 krawędzi, to musi on być spójny.
Graf prosty
Chodzi o to że gdy weźmiemy \(\displaystyle{ n-1}\) wierzchołków z tego grafu oraz \(\displaystyle{ {n-1 \choose 2}}\) krawędzi to powstanie graf pełny, zostaje nam tylko jeden wolny wierzchołek oraz co najmniej jedna krawędź więc graf musi być spójny