Nie da się narysować grafu o spełniającego powyższy warunek.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)}}\)
Można jakoś "ładnie" dowieść, że się nie da
Zadanie 2.
Drzewo - graf spójny, acykliczny. Drzewo nie ma żadnych cykli, więc jest tylko jedna możliwość wyboru drogi.Pokaż, że każde dwa wierzchołki są połączone w drzewie dokładnie jedną ścieżką.
Zadanie 3.
Bez pomysłu, ale przeczuwam jakiś dowód nie-wprost.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.
Zadanie 4.
Drzewo nie ma cykli, więc nic nie stoi na przeszkodzi na podział wierzchołków na dwa niezależne zbiory.Wykaż, że każde drzewo jest grafem dwudzielnym. Które drzewa są pełnymi grafami dwudzielnymi?
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.