NR	PYTANIE	TAK/NIE
1.	Każdy acykliczny podzbiór zbioru krawędzi grafu spójnego można uzupełnić do drzewa rozpinającego.	TAK
2.	Istnieje liczba naturalna n taka że K(G)>n implikuje, że G ma cykl Hamiltona.	NIE
3.	Jeśli χ(G)≤4 to G jest planarny	NIE
4.	Każdy graf planarny można narysować na torusie (bez przecinania krawędzi)	TAK
5.	Jeśli G jest grafem Eulera to L(G) jest grafem Hamiltona.	TAK
6.	G lub dopG jest grafem spójnym.	TAK
7.	Jeśli G ma 1-faktor to dla każdego zbioru krawędzi S liczba nieparzystych składowych grafu G-S nie przekracza liczności zbioru S	NIE?
8.	Nie istnieje 6-spójny graf planarny	TAK
9.	Każde dwie najdłuższe drogi proste w G mają wspólny wierzchołek.	TAK
10.	Graf Petersena jest planarny.	NIE
11.	Każdy graf Hamiltona jest dwuspójny.	TAK
12.	Dla każdego drzewa T nie mającego wierzchołków stopnia 2, graf G otrzymany z T przez połączenie krawędzią każdych dwóch liści jest grafem Hamiltona.	NIE/TAK*
13.	Dla każdego grafu Hamiltona G, χ'(G)=Δ(G)	NIE
14.	W każdym grafie dwudzielnym o klasach X i Y, α0(G)=min(|X|,|Y|)	NIE
15.	W każdym grafie o co najmniej 3 wierzchołkach istnieją dwa wierzchołki o tym samym stopniu.	TAK

Ad.6. Załóżmy, że G jest niespójny. Jego wierzchołki możemy podzielić więc na dwie klasy G₁ i G₂ rozdzielne, czyli takie, że żaden wierzchołek należący do G₁ nie sąsiaduje z żadnym wierzchołkiem należącym do G₂. Jeżeli teraz weźmiemy dopG to wszystkie wierzchołki z klasy G₁ sąsiadują ze wszystkimi wierzchołkami z klasy G₂. Teraz a) dla dowolnych u∈G₁ i v∈G₂ istnieje u-v droga, bo wzięliśmy dopG, a poprzednio w G nie mieli wspólnej krawędzi oraz b) dla dowolnych u,v∈tej samej składowej grafu G istnieje droga u-z-v, gdzie z∈drugiej składowej. Stąd mamy, że pomiędzy wszystkimi wierzchołkami w dopG istnieje droga ⇒ dopG jest spójny. Analogicznie w drugą stronę.

Ad.8.W każdym grafie planarnym ∃ wierzchołek stopnia ≤5. Usuwamy wierzchołki sąsiadujące z tym wierzchołkiem i w ten sposób rozspójniamy graf (usunęliśmy mniej niż 6 wierzchołków więc powinien być nadal spójny). Zatem nie istnieje 6-spóny graf planarny.

Ad.9.Rys.1.Załóżmy że w G mamy dwie najdłuższe drogi P₁,P₂ które nie mają wspólnego wierzchołka. Niech u∈V(P₁), v∈V(P₂) u≠v. Jednak graf G jest spójny więc dist(u,v)≥ 1. Powstaje nam trzecia dłuższa od P₁,P₂ droga P₃ zawierająca po dokładnie jednej części dróg P₁,P₂ oraz drogę u-v. Jest to sprzeczne, bo P₁, P₂ miały być najdłuższymi drogami.

Ad.10. Graf Petersena nie jest planarny, bo jest ściągalny do grafu K₅, który nie jest planarny. Zatem na mocy tw. Kuratowskiego: Dany graf jest planarny nie zawiera podgrafu homeomorficznego z grafem K₅ lub z grafem K_3,3)RYS.

Ad.13.Kontrprzykład rys.3 Δ(a)=2 χ'(G)=3

Ad.15 W zadaniu tym będę korzystać z zasady szufladkowej. Mamy n wierzchołków, gdzie n≥3. Weźmy szufladki oznaczone liczbami od 0 do n-1 i niech numer szufladki odpowiada stopniowi danego wierzchołka. Aby wykazać, że istnieją w grafie dwa wierzchołki o tym samym stopniu, wykażemy, że jedna z szufladek zawiera więcej niż jeden element. Mamy zatem n wierzchołków i n szufladek, teoretycznie każda z szufladek może być zajęta. Gdyby tak było, to wierzchołek o stopniu 0 nie łączyłby się z żadnym innym wierzchołkiem, a wierzchołek o stopniu n-1 łączyłby się z każdym z wierzchołkiem, również z tym, który ma stopień 0, co jest oczywiście niemożliwe.

---