[DM 2005/05]

Uwaga słowo graf oznacza graf prosty (chyba, że wyraźnie zaznaczono w treści zadania, że chodzi o multigraf).

[1/05] Udowodnij, że każdy graf o liczbie wierzchołków większej niż 1 zawiera co najmniej dwa wierzchołki tego samego stopnia.

[2/05] Z dokładnością do izomorfizmu wyznacz wszystkie grafy:

1. o 4 wierzchołkach

2. kubiczne o 5 wierzchołkach

3. regularne stopnia 4 o 6 wierzchołkach

[3/05] Udowodnij, że w każdym niepustym, regularnym grafie dwudzielnym liczba wierzchołków jest parzysta.

[4/05] Wyznacz promień i średnicę grafów K_n, C_n, W_n, Q_n, K_r,s.

[5/05] Udowodnij, że kostka Q_n jest grafem dwudzielnym.

[6/05] Udowodnij, że wszystkie grafy na rysunku poniżej są izomorficzne:

Czy istnieje spójny graf kubiczny o 10 wierzchołkach, który nie jest izomorficzny z powyższym grafem?

[7/05] Udowodnij, że graf dwudzielny o n wierzchołkach ma co najwyżej n² / 4 krawędzi.

[8/05] Graf izomorficzny, ze swoim dopełnieniem nazywamy grafem samodopełniającym.

1. Udowodnij, że każdy graf dopełniający ma 4k lub 4k + 1 wierzchołków, gdzie k ∈ Z.

2. Wyznacz wszystkie grafy samodopełniające mające 4 i 5 wierzchołków.

3. Znajdź graf samodopełniający mający 8 wierzchołków.

[9/05]* Udowodnij, że graf o 2k wierzchołkach, który nie zawiera trójkątów ma co najwyżej k² krawędzi.

[10/05]* Udowodnij, że jeśli dwa różne cykle w grafie G zawierają tę samą krawędź e, to w grafie G istnieje cykl nie zawierający e.

[11/05] Udowodnij, że graf i jego dopełnienie nie mogą być jednocześnie grafami niespójnymi.

[12/05] Ile automorfizmów mają grafy K_n, C_n, W_n, K_r,s ?

[13/05]* Udowodnij, że w każdym grafie spójnym każde dwie drogi maksymalnej długości mają wspólny co najmniej jeden wierzchołek.

[14/05] Niech r będzie liczbą naturalną. Udowodnij, że jeżeli graf r-regularny ma obwód 5 i promień 2, to ma dokładnie r² + 1 wierzchołków.

[15/05] Udowodnij, że dla każdego spójnego grafu G zachodzi rad(G) ≤ diam(G) ≤ 2 rad(G). Podaj przykłady grafów, dla których zachodzi równość w jednym z dwóch przypadków.

[16/05]* Czy istnieje graf kubiczny, w którym każdy cykl jest tej samej długości?

---