grafy, drzewa

[gosienkaq]

1. Pokaż, że jeżeli T jest drzewem, to dla dowolnych wierzchołków x i y
należących do zbioru V (T) istnieje dokładnie jedna ścieżka o końcach w wierzchołkach x i y. Czy prawdziwe jest twierdzenie odwrotne?
2. Niech G będzie grafem o zbiorze wierzchołków \(\displaystyle{ V(G)={x_{1},.....x_{n}}}\) . Niech
\(\displaystyle{ d_{1} \le d_{2} \le .... \le d_{n}}\), gdzie \(\displaystyle{ d_{i}}\) oznacza stopień wierzchołka \(\displaystyle{ x_{i}}\) dla \(\displaystyle{ i \in {1;.........; n}}\).
Pokaż, że jeżeli \(\displaystyle{ d_{1} \ge 1}\)oraz \(\displaystyle{ \sum_{i=1}^{n}d_{i}=2n-2}\), to G jest drzewem.
3. Pokaż, że w dowolnym grafie G = (V;E) istnieje zbiór cykli o tej własności, że każda krawędź \(\displaystyle{ e \in E}\) należy do dokładnie jednego cyklu z tego zbioru wtedy i tylko wtedy, gdy stopień dowolnego wierzchołka \(\displaystyle{ v \in V}\) jest liczbą parzystą.
4. Pokaż, że kostka \(\displaystyle{ H_{n}}\) ma cykl Hamiltona.
5. Scharakteryzuj grafy pełne \(\displaystyle{ K_{n}}\) posiadaj¡ce cykl Eulera.

Proszę o jakąś pomoc (szczególnie 2 pierwsze zadania) bo mam z tego niedługo koło a nie ogarniam tego

[miodzio1988]

1)Ze spojnosci wynika ze jedna sciezka istnieje. Gdyby istnialy dwie sciezki to wtedy mamy cykl. Zatem musi byc jedna sciezka.
W druga strone chyba tez to jest prawda ale musialbym pomyslec
5)\(\displaystyle{ n}\) powinno byc parzyste. I chyba tyle tylko potrzeba
4)kostka \(\displaystyle{ H_{n}}\) ? Rozwin mysl
2) i 3) na razie nie tykam.
Jakos nie lubie dyskretnej i calej tej teorii grafow dlatego bardzo pomocny nie jestem Ale mam nadzieje ze to co napisalem chociaz troche Ci pomoze