1. Każdy pięciospójny graf planarny ma co najmniej 12 wierzchołków.

2. Graf Petersena nie jest planarny.

3. Nie istnieje graf planarny o 5-regionach taki, że każde dwa mają wspólną krawędź.

4. Udowodnić, że K_3,3 i K₅ nie są planarne.

5. Udowodnić, że graf planarny nie zawierający cyklu długości 3 można pokolorować 4 kolorami.

6. Graf planarny może być umieszczony na powierzchni kuli.

7. Pokazać, że G lub dopG nie jest planarny.

8. G-spójny, k-regularny, |V|=p χ(G)>=p/p-k.

9. Znaleźć graf o własnościach: K(G)=a, χ(G)=b, δ(G)=c 1<a<b<c.

10. |E(G)|>=(χ(G) nad 2).

11. χ(G)*χ(dopG)>=|V|=p.

11a. Znaleźć wszystkie grafy spójne takie, że χ(G)=3 i G krytyczny.

12. G jest k-regularny |V|=2n+1 χ'(G)=k+1

13. Pokazać, że χ(G1+G2)=χ(G1)+χ(G2)

14. Graf dwudzielny każdy cykl ma długość parzystą

15. ∀v deg v>(n-1)/2 G ma cykl Hamiltona

16. Znajdź najmniejsze n takie, że ∀ grafu o n wierzchołkach G ma cykl lub dopG ma cykl

17. G(V,E) |E|>=(n² -3n+6)/2 G ma cykl Hamiltona

17a .Każdy graf Ks+1 ma 2-faktoryzację ma cykl Hamiltona

18. G zawiera cykl Eulera zawiera pewien cykl prosty

19. G-spójny G³ graf Hamiltona

19a. |E|>=2 K(G)>=2(∀ e,f ∈E) e,f≠0 ∃ cykl prosty taki, że e,f ∈E(L) tzn. każde dwie sąsiednie krawędzie leżą na wspólnym cyklu prostym.

20. Dwudzielny graf Hamiltona ma parzystą liczbę wierzchołków

21. |V|>=5 (∀u,v ∈V) ∃ u-v droga Hamiltona to K(G)>=3

22. G-spójny 3-regularny Hamiltonowski χ'(G)=3

23. δG)=d G zawiera cykl prosty długości >= d+1

24. Czy prawdą jest że, jeśli G=(V,E) w: ER+ jest różnowartościowe to G ma dokładnie jedno drzewo rozpinające

25. T-drzewo ∀x,y ∈V x≠y istnieje w T do 3 x-y droga Hamiltona (jest cykl hamiltona)

26. T-drzewo ≡∀ T1, T2 spójnych podgrafów T zachodzi T1∩T2≠0 T1∩T2 jest spójnym podgrafem T

27. diam G G ma drzewo rozpinające T takie, że diam T=2

28. T1, T2- drzewa rozpinające. Ud. że w T2 ∃ krawędź f taka, że T1-c+f jest drzewem rozpinającym

29. diamG=2 G ma drzewa rozpinające takie, że diamT=2

30. α0(G)>=β1(G) α1(G)>=β0(G)

31. α0(G)+β0(G)=|V|+n

32. Scharakteryzować grafy dla których α1=β1?

33. α0>=δ(G)

34. α0(G)>=β1(G)

35. α1=β1 |V|=p

36. G-dwudzielny |E|<=α0*β0

37. K(G-x)>=K(G)-1 G-spójny

38. K(G*G)>=n |V|>=n+1 G-spójny

39. G-spójny ∀ podziału V=V1+V2 V1, V2≠0 V1∩V2=0 ∃ krawędzie u, v takie, że u∈V1 v∈V2

40. ∀G G-spójny każde dwie najdłuższe drogi mają wspólny wierzchołek

41. |E(G)|>=(n-1 nad 2)+1 to G jest spójny

42. |K(G)|=K(G)-1 gdzie G-spójny

43. to samo co 45

44. G-spójny to |V(G)|>=K(G)*(diam(G)-1)+2

45. G-spójny |V|>=3 => G² dwuspójny

46. G-dwuspójny ∀x,y,z z V ∃ x-y droga przechodząca przez z.

47. W grafie spójnym max. liczba rozłącznych zbiorów u-v dzielny jest równa dist(u,v)-1

48. K(G)>=2 G zawiera drogę długości 1 G zawiera cykl długości > √2*L

49. K(G)=k |V|=n |E|>= k*n/2

50. G≡dop.G |V|>1 diamG=2 lub diamG=3

51. Jakie muszą być liczby p i n, żeby istniał n-regularny graf o n wierzchołkach?

52. ∀G |V|=G G lub dop.G zawiera k3

53. Jaka jest najmniejsza ilość krawędzi w grafie o n wierzchołkach

54. K(G)=χ(G)<=δ(G)=min deg(v)

55. Każdy graf Kis ma 1-fakt. ∀s>=1

56. Dla jakich n można obejść szachownicę n*n tak, aby wrócić do początku?

57. V=(v1, ..., vl) a ∈{0,1} (v1, v2) ∈E jeśli różnią się na doładnie jednym miejscu a)Qk jest regularny b) znaleźć liczbę krawędzi i wierzchołków

58. Macierz - kwadrat łaciński

59. dopG ≡ G graf G jest izomorficzny ze swoim dopełnieniem (|V|=4k lub |V|=4k+1)

60. G lub dopG spójny

61. Ile jest liści w drzewie T w którym jest n wierzchołków o stopniu i i=2,3, …=max degv

62. G-dwuspójny każde dwie sąsiadujące krawędzie leżą na wspólnym cyklu prostym

63. Pewna grupa Arabów wita się, podając sobie ręce. Nikt nie wita się z samym sobą i żadna para osób nie wita się więcej niż jeden raz. Pokazać, że w grupie muszą być dwie osoby, które ściskały taką samą liczbę dłoni.

64. Pokazać, że jeżeli na tarczy kołowej o promieniu 1 umieścimy 7 punktów w ten sposób, że żadne dwa nie są odległe od siebie o mniej niż 1, to jeden z punktów będzie w środku tarczy, a pozostałych sześć będzie tworzyć na obwodzie tarczy sześciokąt.

65. Pokazać, że dla dowolnych n dodatnich liczb całkowitych istnieje podzbiór, którego suma elementów jest podzielna przez n.

66. Pokazać, że w każdym grafie liczba wierzchołków stopnia nieparzystego jest parzysta.

67. Pokazać, że w grafie dwudzielnym każdy cykl składa się z parzystej liczby krawędzi.

68. Wyznaczyć dla skoczka trasę po szachownice tak, że zanim powróci on na pole, z którego wystartował, odwiedzi dokładnie raz każdy kwadrat szachownicy.

69. Pokazać, że jeżeli G jest grafem o nieparzystej liczbie wierzchołków, z których każdy ma stopień d większy od zera, to nie można pokolorować krawędzi grafu G za pomocą d kolorów.

70. Udowodnij, że w grupie sześciu osób zawsze istnieją albo trzy osoby znające się nawzajem, albo trzy osoby, z których żadna nie zna pozostałych dwóch.

71. Udowodnij, że jeśli G jest grafem dwudzielnym, to każdy cykl w G ma długość parzystą.

72. Udowodnij, że jeśli w grafie G każdy wierzchołek ma stopień równy co najmniej 2, to graf G zawiera cykl.

73. Graf K_n ma n^n-2 drzew spinających.

74. Wykaż, że dla każdej liczby naturalnej n, graf związany z alkoholem C_nH_2n+1OH jest drzewem (wierzchołek odpowiadający atomowi tlenu ma stopień 2).

75. Niech G będzie grafem prostym, mającym n wierzchołków. Jeśli graf G ma k składowych, to liczba m jego krawędzi spełnia nierówności: n-k≤m≤(n-k)(n-k+1)/2.

76. Rozważmy szachownicę wymiaru n×n. Dla jakich wartości n można znaleźć dla skoczka trasę dookoła szachownicy, w której każdy z możliwych ruchów jest wykonany dokładnie raz (w jednym lub drugim kierunku)?

77. Znaleźć przykład grafu G, który jest eulerowski i którego dopełnienie jest również grafem eulerowskim.

78. Szalony kartograf stworzył mapę rysując n okręgów, niekoniecznie równych promieni. Jaka jest najmniejsza liczba kolorów, którymi można ją pokolorować tak, że sąsiednie okręgi mają różne kolory?

79. Indeks chromatyczny grafu pełnego Kn wynosi: χ'(K_n)=n-1 dla n parzystych i χ'(K_n)=n dla n nieparzystych.

80. Niech (V₁,V₂,E) będzie grafem dwudzielnym o największym stopniu wierzchołka = d. Wówczas χ'(G)=d.

81. Niech G=(V,E) będzie grafem, w którym największy stopień wierzchołka wynosi d. Wówczas krawędzie grafu G można pokolorować przy użyciu d+1 kolorów; tj. d≤χ(G)≤d+1.

82. Skończony graf spójny, mający dokładnie dwa wierzchołki stopnia nieparzystego, ma drogę Eulera.

83. Jeśli G jest grafem prostym, w którym największy stopień wierzchołka jest Δ, χ(G)=Δ+1.

84. Każdy planarny graf prosty zawiera wierzchołek stopnia co najwyżej 5.

85. Każdy planarny graf prosty G jest 6 - kolorowalny. (χ(G)=6)

86. G-rysunek płaski n-m+f=2

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.

---