[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:
o 4 wierzchołkach
kubiczne o 5 wierzchołkach
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 Kn, Cn, Wn, Qn, Kr,s.
[5/05] Udowodnij, że kostka Qn 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 n2 / 4 krawędzi.
[8/05] Graf izomorficzny, ze swoim dopełnieniem nazywamy grafem samodopełniającym.
Udowodnij, że każdy graf dopełniający ma 4k lub 4k + 1 wierzchołków, gdzie k ∈ Z.
Wyznacz wszystkie grafy samodopełniające mające 4 i 5 wierzchołków.
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 k2 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 Kn, Cn, Wn, Kr,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 r2 + 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?