Zadania z grafów
: 4 wrz 2007, o 14:01
1. Pokaż, że w dowolnym drzewie \(\displaystyle{ \Delta}\)(T) istnieje co najmniej wierzchołków stopnia 1.
2. W grafie G istnieje tylko 1 cykl. Pokazać, że \(\displaystyle{ \chi(G)}\)\(\displaystyle{ \leqslant 3}\)
3. Pokaż, że nie istnieje 4-regularny graf dwudzielny, który jest planarny.
Można prosić o wskazówki jak je rozwiązać?
2. W grafie G istnieje tylko 1 cykl. Pokazać, że \(\displaystyle{ \chi(G)}\)\(\displaystyle{ \leqslant 3}\)
3. Pokaż, że nie istnieje 4-regularny graf dwudzielny, który jest planarny.
Można prosić o wskazówki jak je rozwiązać?