Matematyka dyskretna, zadanie nr 4776
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
brightnesss post贸w: 113 |  2016-08-13 16:04:41Pokaza膰 偶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