Matematyka.pl

mam problem z takimi zadaniami, a zbliza sie kolokwium, wiec z gory dzieki za pomoc

1) Wykaz, ze drzewo bez wierzcholkow stopnia 2 ma wiecej lisci niz innych wierzcholkow.

2) Pokaz, ze kostka \(\displaystyle{ H _{n}}\) jest grafem dwudzielnym.

1. indukcja
2. Dwupodział będze taki:
niech \(\displaystyle{ g}\) to jakiś ustalony wierzchołek:
\(\displaystyle{ A=\{h:\mbox{można dojsc od g do h po scieżce parzystej długości}\}}\)
\(\displaystyle{ B=\{h:\mbox{można dojsc od g do h po scieżce nieparzystej długości}\}}\)

Trzeba pokazać, że te zbiory są rozłączne.

dzieki, ale jeszcze mam problem:

1) nie zabardzo rozumiem jak z indukcja, w rozwiazaniach z wykladu mam cos takiego, ale nie rozumiem skad to sie bierze:

2 * E = l*1 + \(\displaystyle{ \sum_{0}^{n-l} l_{i} \ge}\)l+3(n-l)

2(n-1) \(\displaystyle{ \ge}\) l+3(n-l)
skad te dzialamnia sie biora?

2) ok, pokazalem ze istnieje u mnie zbior B, ale nie moge znalezc zadnej sciezki parzystej pomiedzy g i h, czy ona napewno jest?