Własności drzew, ciąg stopni grafu prostego

[Szemek]

Zadanie 1.

Zbadaj, które z wymienionych poniżej ciągów są ciągami stopni pewnego grafu prostego. Narysuj przykładowe grafy realizujące ciągi, lub uzasadnij dlaczego jest to niemożliwe.
c) \(\displaystyle{ \text{(4; 4; 3; 2; 1)}}\)

Nie da się narysować grafu o spełniającego powyższy warunek.
Można jakoś "ładnie" dowieść, że się nie da

Zadanie 2.

Pokaż, że każde dwa wierzchołki są połączone w drzewie dokładnie jedną ścieżką.

Drzewo - graf spójny, acykliczny. Drzewo nie ma żadnych cykli, więc jest tylko jedna możliwość wyboru drogi.

Zadanie 3.

Pokaż, że w dowolnym drzewie o co najmniej dwóch wierzchołkach istnieją, co najmniej dwa wierzchołki stopnia 1 (liście). Pokaż, że dowolne drzewo \(\displaystyle{ G}\), w którym \(\displaystyle{ \Delta (G) \ge k, \; k\ge 2}\) ma co najmniej \(\displaystyle{ k}\) liści.

Bez pomysłu, ale przeczuwam jakiś dowód nie-wprost.

Zadanie 4.

Wykaż, że każde drzewo jest grafem dwudzielnym. Które drzewa są pełnymi grafami dwudzielnymi?

Drzewo nie ma cykli, więc nic nie stoi na przeszkodzi na podział wierzchołków na dwa niezależne zbiory.
Gwiazdy są przykładem drzew, które są pełnymi grafami dwudzielnymi. \(\displaystyle{ K_{1,n}}\)

Będę wdzięczny za wskazówki, pomysły jak te zadania zrobić, aby wszystko formalnie zapisać.
Z góry dzięki.

[abc666]

Co do pierwszego, skoro mamy pięć wierzchołku a dwa mają stopień 4 to są połączone z każdym z pozostałych wiec jeden z wierzchołków nie może mieć stopnia 1

[Szemek]

Faktycznie, takie wyjaśnienie wystarczy.

Może ktoś ma jeszcze jakieś pomysły do pozostałych zadań?
Szczególnie druga część zadania 3.

[miodzio1988]

Trochę wypiłem dzisiaj, ale z wielkiej sympatii podrzucę kilka pomysłów (jutro rzeczowe pomysły )
2) Niby dobrze, ale można to zrobić nie-wprost. Zalóżmy, że są dwie ścieżki wtedy będziemy mieli cykl. I tyle. Chociaż Twoja argumentacja też jest dobra
3)Weż sobie najdluższą drogę w drzewie. I patrz na końce tej drogi. Jeśli nie są te końce liściami to znaczy, że ...i tutaj pojawiają sie dwie sprzeczności: pojawia się cykl albo droga nie byla najdluzsa. dasz radę teraz. Dla k liści dowod indukcyjny Ale nad tym pomyslę, ok??
4)Jak pokazać dwudzielność. Wez dowolny wierzcholek i go zawieś na suficie. Reszta wierzcholkow z niego "zwisa". Birzemy co drugi "poziom" . Sprobuj sobie to narysowac. Wtedy to klasy tego grafu to będą własnie wierzchołki brane co drugi poziom. Jutro rano dam coś bardziej zrozumiałego. Mam nadzieję, że to co napisałem jest dosyć jasne.

Gdybyś czegoś nie rozumiał to pisz na prv pozdro;]

[Szemek]

Pierwsza część zadania 3:
\(\displaystyle{ T}\) - drzewo

\(\displaystyle{ ||T|| = n - 1 \\
\sum_{v \in V(T)} \deg (v) = 2n-2}\)

Nie-wprost:
1. Załóżmy, że stopień każdego wierzchołka jest większy bądź równy 2
\(\displaystyle{ \forall_{v\in V(T)} \deg (v) \ge 2 \Rightarrow \sum_{v\in V(T)} \deg (v) \ge 2n}\)
Sprzeczność, a więc musi istnieć co najmniej jeden wierzchołek stopnia 1.
2. Załóżmy, że stopień jednego wierzchołka jest równy 1 oraz stopień pozostałych wierzchołków jest większy bądź równy 2.
\(\displaystyle{ \left. \begin{matrix} \deg (v_k) = 1 \\ \forall_{v\in V(T) \setminus \{v_k\}} \deg (v) \ge 2 \end{matrix} \right\} \Rightarrow \sum_{v\in V(T)} \deg (v) \ge 2n-1}\)
Sprzeczność, a więc musi istnieć co najmniej dwa wierzchołki stopnia 1.

Z dowodem drugiej części utknąłem.
miodzio1988, jak wpadniesz jak dowieść tę drugą część, to będę wdzięczny.
Co do zadania 4. Tak na oko, to od razu widać, że drzewo można spokojnie rozrysować jako graf dwudzielny. Ale jak to opatrzyć "ładnym i naukowym" komentarzem, sformułowaniem Bo o zawieszaniu na suficie, to raczej na egzaminie lepiej nie pisać

[miodzio1988]

To już jutro Szemek wszystko Ci opiszę w szczegółach, ok? Edytuję post i Ci dam na prv znać na co wpadłem ( robiłem ten dowód kiedyś więc spokojnie możesz liczyć na rzeczowe uzasadnienie) . A tę dwudzielność tak się robi możesz jeszcze zamiast tych poziomów brać odległości od danego wierzchołka. Ale o tym jutro
Pozdro;]

[Szemek]

Co do zadania 3
Udało mi się znaleźć dowód do prawie identycznego zadania, który wygląda następująco:

Treść:
Brualdi, sec. 11.8 Exercises, 62.:
Prove that if a tree has a vertex of degree \(\displaystyle{ p}\), then it has at least \(\displaystyle{ p}\) pendent vertices.
Udowodnij, że jeśli drzewo ma wierzchołek stopnia \(\displaystyle{ p}\) to posiada co najmniej \(\displaystyle{ p}\) wiszących wierzchołków.
(wiszący wierzchołek = liść = wierzchołek stopnia 1)
źródło:

Niech \(\displaystyle{ (d_1,d_2,...,d_n)}\) będzie drzewem o \(\displaystyle{ n}\) wierzchołkach. Ponieważ drzewo jest grafem spójnym mamy zależność \(\displaystyle{ d_1 \ge d_2 \ge ... \ge d_n \ge 1}\). Niech \(\displaystyle{ k}\) będzie liczbą wiszących wierzchołków.
Wtedy:
\(\displaystyle{ d_i = 1}\) dla \(\displaystyle{ i=n-k+1,n-k+2,...,n}\)
\(\displaystyle{ d_i\ge 2}\) dla \(\displaystyle{ i=1,2,3,...,n-k-1,n-k}\)
a więc:
\(\displaystyle{ 2(n-1) = d_1 + d_2 + ... + d_{n-k} + d_{n-k+1} + ... + d_n = \\ = d_1 + (d_2 + ... + d_{n-k}) + k \ge d_1 + 2(n-k-1) + k = d_1 + 2(n-1) - k}\)
otrzymaliśmy nierówność:
\(\displaystyle{ 2(n-1) \ge d_1 + 2(n-1) - k \\
0 \ge d_1 - k \\
k \ge d_1}\)
Teraz dla każdego wierzchołka \(\displaystyle{ p=\deg(v)}\) mamy \(\displaystyle{ k \ge d_1 \ge p}\), tzn. w drzewie jest co najmniej \(\displaystyle{ p}\) wiszących wierzchołków.

Wracając do zadania 3.
Jeżeli maksymalny stopień wierzchołka w drzewie jest większy bądź równy \(\displaystyle{ k}\), to na podstawie powyższego dowodu możemy stwierdzić, że drzewo posiada co najmniej \(\displaystyle{ k}\) liści.

miodzio1988, jeśli masz inny dowód do tego zadania, to chętnie go zobaczę.