Matematyka dyskretna, zadanie nr 4776

Autor	Zadanie / Rozwiązanie
brightnesss postów: 113	2016-08-13 16:04:41 Pokazać że jeśli $\delta$(G)>podłoga z ($\frac{n}{2}$-1) to graf G jest spójny.

tumor postów: 8070	2016-08-15 19:32:30 Przypuśćmy, że graf G nie jest spójny, czyli składa się ze spójnych grafów $G_1,G_2,...,G_k$. Wówczas dla każdego z grafów $G_i$ musi być prawdą $\delta(G_i)> \lfloor{\frac{n}{2}}\rfloor-1$, wobec tego grafy $G_i$ mają więcej niż $\lfloor{\frac{n}{2}}\rfloor$ wierzchołków. Jeśli są co najmniej dwa grafy $G_i$, to w sumie dają więcej niż n wierzchołków. Sprzeczność.

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj