Udowodnij, że na każdym przyjęciu są dwie osoby o takiej samej liczbie
znajomych.
Udowodnij, że przynajmniej jeden z grafów G, G' (dopełnienie) jest spójny. Niech diam(G) oznacza średnicę grafu G (nieskończoność jeśli G jest niespójny) i niech f(G) = min(diam(G), diam(G')). Znajdź sup f(G) po wszystkich grafach G.
Udowodnij, że w K6 dowolnie pokolorowanym krawędziowo na 2 kolory jest
monochromat. trojkat (są nawet dwa!), ale w K5 niekoniecznie.
Rozstrzygnij, czy istnieje:
a) graf o ciągu stopni wierzchołków (3 3 3 3 5 6 6 6 6 6 6)
b) (3 3 3 3 3 5 6 6 6 6 6 6)
c) dwudzielny (3 3 3 3 3 5 6 6 6 6 6 6)
d) drzewo (dowolny ciąg długości n o sumie 2n-2)
Podaj przykład dwóch nieizomorficznych grafów spójnych o takich samych
ciągach stopni wierzchołków.
Graf niezorientowany jest orientowalny, jeśli można na jego krawędziach
dorysować strzałki tak, żeby dostać digraf silnie spójny. Pokaż, że graf spójny
jest orientowalny wtedy i tylko wtedy, gdy nie ma mostów.