Matematyka dyskretna, zadanie nr 4665

Autor	Zadanie / Rozwiązanie
brightnesss postów: 113	2016-06-06 21:43:08 Pokazać, że jeśli $\delta(G)> $ (podłoga z) $\frac{n}{2}-1$ to G jest spójny. bierzemy podłogę z liczby tylko $\frac{n}{2}$ Przepraszam, nie wiedziałam jak to zapisać

janusz78 postów: 820	2016-06-07 16:01:44 Jeżeli rozważymy składową o najmniejszej liczbie wierzchołków to liczba jej wierzchołków wynosi co najmniej $ 1 + \frac{n}{2}> \frac{n}{2}$. Więc z nierówności: $ \delta(G)> \lfloor \frac{n}{2}-1 \rfloor $ wynika, że jest tylko jedna taka składowa, czyli graf jest spójny.

strony: 1

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