Zadanie 1

Centrum grafu G to zbiór wierzchołków v, dla których max_w d(v,w) jest najmniejsze. Udowodnij, że centrum drzewa to pojedynczy wierzchołek albo para wierzchołków połaczonych krawędzią.

Zadanie 2

Udowodnij twierdzenie Cayleya o zliczaniu drzew etykietowanych: K_n ma n^n-2 drzew rozpinających
(a) wskazując bijekcję między takimi drzewami a (n-2)-ciągami o elementach ze zbioru {1,...,n} (kody Prufera);
(b) sumując liczby drzew o ustalonym układzie stopni wierzchołków.

Zadanie 3

Podaj przykłady grafów na wszystkie cztery kombinacje:
(istnieje/nie istnieje) x (cykl Eulera/cykl Hamiltona)

Zadanie 4

Udowodnij, ze jeśli G jest spójny o k>0 wierzchołkach nieparzystych stopni,
to k jest parzyste i k/2 jest najmniejszą liczbą krawędziowo rozłącznych
łańcuchów pokrywających wszystkie krawędzie G.

Zadanie 5

Z kompletu 28 kamieni domina (od 0-0 do 6-6) usuwamy kamienie 0-1, 0-2,
0-3. Ile jeszcze trzeba usunać, żeby resztę dało się ułożyć w łańcuch
zamknięty?

Zadanie 6

Które pełne grafy dwudzielne i trójdzielne są eulerowskie?
hamiltonowskie?

Zadanie 7

Pokaż, że graf Petersena jest maksymalny niehamiltonowski.

Zadanie 8

Pokaż, że turniej jest hamiltonowski <=> jest silnie spójny.

Zadanie 9

Udowodnij, że jesli z kodu Graya zdefiniowanego rekurencyjnie
G(0) = pusty ciąg; G(n+1) = (0G(n); 1G(n)^R)
wypisać wektory zawierające k jedynek, to dwa sąsiednie (cyklicznie)
wektory mają odległość Hamminga równą 2. Napisać wzór rekurencyjny na taki
'okrojony' kod Graya G(n,k).