1. Każdy pięciospójny graf planarny ma co najmniej 12 wierzch.

Z tego ze K(G)≤δ(G) (minimalny stopień wierzch.) Graf pięciospójny ma wszystkie wierzch. stopnia co najmniej piątego. ∀G ∑deg v=2|E| czyli ∑deg v/|V|≥|E| ⇒|V|5/2≤|E| (liczba krawędzi). Wniosek z Tw. Eulera G spójny planarny o n wierzch. i m krawędziach to m≤3n-6 skoro nasz graf planarny więc |E|≤3|V|-6 czyli 5|V|/2≤|E|≤3|V|-6⇒ 5|V|/2≤3*|V|-6 ⇒ (5|V|-6|V|)/2≤ (-6)⇒ -|V|/2≤ (-6)⇒ |V|≥12.

2. Graf Petersena nie jest planarny

Dla grafu Petersena obwód r wynosi 5 (tzn. najkrótszy cykl ma pięć krawędzi). Ponadto |E|=15 i |V|=10. W ten sposób korzystając z wniosku: Niech G=(V,E) będzie grafem planarnym, zawierającym cykl i, w którym liczba krawędzi w najkrótszym cyklu jest równa r (liczba ta nazywa się obwodem grafu G). Wówczas (r-2)|E|≤r(|V|-2), doszliśmy do tego, że 45=(r-2)|E|≤ r(|V|-2)=40 co jest nieprawdą. Zatem graf Petersena nie jest planarny. RYS

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

Zakładamy, że istnieje graf planarny G o f=5. Konstruujemy graf dualny do G. W każdym regionie stawiamy kropkę. Ponieważ istnieje krawędź wspólna dla każdych dwóch regionów to można przejść z regionu do regionu po krawędzi łączącej dwie kropki czyli nasze wierzchołki leżące na wybranych regionach. Dana krawędź nie będzie przechodzić przez żaden inny region gdyż istniała krawędź rozgraniczająca te dwa regiony. W rezultacie dostaniemy graf K₅, który nie jest grafem planarnym! Nie istnieje więc graf dualny do wejściowego bo dualny musi być grafem planarnym. Korzystając z tw, Graf jest grafem planarnym ⇔ gdy ma graf dualny, wnioskujemy, że nie może istnieć graf planarny o 5 regionach taki, że każde dwa mają wspólną krawędź. Dowód twierdzenia: Wystarczy udowodnić, że jeśli graf G ma graf dualny G*, to G jest grafem planarnym. Dowód przeprowadza się w 4 fazach. 1. Jeśli graf G ma graf względem niego dualny, to także każdy podgraf grafu G ma graf względem siebie dualny. Jest to następstwo tego, że usunięcie krawędzi z grafu G odpowiada w grafie G* eliminacja odpowiedniej krawędzi, a ta operacja nie narusza planarności grafu. 2. Jeśli graf G ma graf dualny, a graf G' jest homeomorficzny względem grafu G, to graf G' ma także graf dualny. Wynika to z tego, że odpowiednikiem dołączenia lub usunięcia z grafu G wierzchołka drugiego stopnia jest dołączenie lub usunięcie w grafie dualnym równoległej krawędzi do jednej z krawędzi istniejących, a ta operacja nie narusza planarności grafu. 3. Grafy K₅ i K_3,3 nie mają grafów dualnych. 4. Przypuśćmy teraz, że G jest grafem planarnym i że ma graf dualny G*. Musi on zawierać podgraf H homeomorficzny względem grafu K₅ lub K_3,3. Wtedy jednak zgodnie z punktami 1. i 2. podgraf H powinien mieć graf dualny, a więc i grafy K₅ lub K_3,3 powinny mieć grafy dualne, co przeczy punktowi 3. Tak więc graf G ma graf względem niego dualny tylko wtedy, kiedy jest planarny. Z kolei, jeśli G jest grafem planarnym, to ma graf dualny.

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

K₅: gdyby był planarny to korzystając z wniosku, że jeżeli G=(V,E) jest grafem planarnym, takim że |V|≤3, to |E|≤3|V|-6 mielibyśmy |E|≤3|V|-6. Ale dla grafu pełnego na pięciu wierzch.ch |V|=5 i |E|=10. Tak więc 10≤9 co jest nieprawdą. Zatem doszliśmy do sprzeczności, a stąd wynika, że K₅ nie jest planarny.

K_3,3: Dla tego dwudzielnego grafu pełnego mamy |V|=6, |E|=9, a więc korzystając z wniosku, że jeżeli G=(V,E) jest planarnym grafem dwudzielnym, takim że |V|≥3, to |E|≤2|V|-4 otrzymujemy 9≤8 co jest nieprawdą. Zatem K_3,3 nie jest planarny.

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

Tw. Brooksa Niech G=(V,E) będzie spójnym grafem o największym stopniu wierzchołka równym Δ(G). Jeżeli G jest grafem pełnym lub składa się z pojedynczego cyklu o nieparzystej liczbie krawędzi, to χ(G)=Δ(G)+1. We wszystkich pozostałych przypadkach χ(G) ≤Δ(G). G- pełny każda krawędź należy do co najmniej dwóch regionów a każdy region jest otoczony co najmniej 4 krawędziami (3 nie mogą być bo nie ma cyklu dł.3). 4f≤2k f≤ ½ k f=k-n+2≤ ½ k 2k-2n+4≤k k≤2n-4. Gdyby δ(G) ≥5 to k≥5n/2 a k≤2n-4 sprzeczność, więc δ(G) <5. Należy udowodnić, że χ(G) ≤4. Indukcja względem n. Dla n=1, 2, 3, 4 - oczywiste. Weźmy graf G, |V|=n+1. ∃v∈G deg_Gv≤4. Wyrzucamy wierzchołek v z G. Z zał. indukcyjnego G-v da się pokolorować 4 kolorami. RYS1. Jeżeli sąsiedzi v pokolorowani są mniejszą ilością kolorów niż 4 to v kolorujemy czwartym kolorem. Zakładam, że sąsiedzi v pokolorowani są 4 kolorami (v₁,v₂,v₃,v₄). Niech G_ij - graf indukowany przez f^-1({c_i,c_j}) przez wierzchołki pomalowane na kolor c_i lub c_j. Rozważmy G_1,3. Jeżeli v₁ i v₃ leżą w różnych składowych grafu to w jednej z tych składowych zamienimy kolory i tak, np. wierzchołek v₁ malujemy kolorem c₃, v można pomalować na kolor c₁. Jeśli v₁ i v₃ leżą w tych samych składowych to v₂ i v₄ leżą w różnych składowych grafu G_2,4. W G_1,3 istnieje droga v₁-v₃ złożona z c₁ i c₃ kolorów. RYS2. Jeżeli jest wierzchołek 4 to sprzeczność bo nie może on być jednocześnie pomalowany na c₁ lub c₃ i pomalowany na c₂ lub c₄. G_2,4 rozpatrujemy w ten sam sposób jak G_1,3.

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

„<=”Rozważmy płaszczyznę dwuwymiarową P , na której ułożono graf płaski G. Wybierzmy dowolny punkt A₀ tej płaszczyzny i umieśćmy sferę trójwymiarową S o dowolnym skończonym promieniu na płaszczyźnie P tak aby punkt A₀ był punktem styczności sfery do płaszczyzny. Następnie oznaczmy symbolem A₁ punkt na sferze przeciwległy do A₀. Punkty A₁ i A₀ wyznaczają na sferze S jej bieguny północny i południowy. RYS. Jeśli teraz połączymy A₁ linią prostą l_i z dowolnym punktem a_i leżącym na płaszczyźnie P, to wyznacza ona na sferze S w sposób jednoznaczny punkt a_i' . Tak więc uzyskaliśmy jednoznaczne i odwracalne odwzorowanie punktów płaszczyzny P, znajdujących się na sferze S, w skończonej odległości od A₀, przy czym punkt A₀ został odwzorowany w samego siebie, punkty płaszczyzny nieskończenie odległe od punktu A₀ zostały jednoznacznie odwzorowane w punkt A₁. Następstwem tego jest jednoznaczne i odwracalne zrzutowanie grafu G na sferę S.

„=>”Zwróćmy uwagę że graf G' zrzutowany (rzut planarnego grafu G) na sferę wyznacza na niej regiony w zasadzie równoważne : odpowiednikiem regionu zewnętrznego grafu płaskiego jest tu region zawierający biegun północny A₁, ułożenie grafu G' na sferze S nie ulegnie istotnej zmianie, jeśli dokonamy obrotu sfery , tak że położenie biegunów się nie zmieni.

7. |G|≥11. Pokazać, że G lub dop.G nie jest planarny.

K=G∪dopG K- graf pełny. Dla grafu pełnego liczba krawędzi wynosi |V|(|V|-1)/2, gdzie |V|- liczba wierzchołków w grafie K. Zakładam, że G i dopG są grafami planarnymi. Z tw. Eulera mamy |E(G)|≤3|V|-6 i |E(dopG)| ≤ 3|V|-6. Zatem 3|V|-6+3|V|-6 ≤|V|(|V|-1)/2 więc |V|²-13|V|+24≥0 Δ=73 |V|_1,2=(13+(-)√(73))/2 ale liczba wierzchołków nie może być liczbą niewymierną. Stąd nie może być tak, że G i dopG są jednocześnie grafami planarnymi, zatem jeden z nich nie jest planarny.

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

Jeśli c_i jest liczbą wierzchołków pokolorowanych kolorem i dla 1≤i≤χ(G), to c_i≤p-k. Zatem p=c₁+c₂+…+c_χ(G)≤χ(G)(p-k), a więc χ(G)≥p/(p-k).

10. Wykazać, że jeśli G- spójny, |E|≥1 to |E(G)| ≥ (χ(G) nad 2)

Graf G kolorujemy na χ(G)=k kolorów. Taki graf składa się z k podgrafów, z których każdy jest grafem niezależnym o wierzchołkach pomalowanych na ten sam kolor. Każdy z podgrafów musi być połączony ze wszystkimi innymi podgrafami przynajmniej jedną krawędzią więc tych krawędzi będzie co najmniej tyle, co w grafie pełnym o k wierzchołkach. E≥k(k-1)/2=χ(G)(χ(G)-1)/2=(χ(G) nad 2) |E|≥ (χ(G) nad 2)

11. Liczby chromatyczne χ(G) i χ(dop G) grafu G o n wierzchołkach spełniają

1) 2 √n ≤ χ(G) + χ(dop G) ≤ n+1

2) n ≤ χ(G)χ(dopG) ≤ 1/4 (n+1)²

Dla dowolnych dwóch licz rzeczywistych a i b zachodzi nierówność (a+b)²≥4ab, wobec tego podstawiając za a=χ(G) i b=χ(G)otrzymujemy (χ(G) +χ(dopG) )²≥4χ(G)χ(dopG)

Prawa strona nierówności pierwszej czyli χ(G) + χ(dopG) ≤ n+1 jest spełniona dla n=1 oraz dla n=2; dla większych wartości n można ją udowodnić metodą indukcji, zakładając słuszność wyrażenia dla pewnego n. Biorąc pod uwagę, iż G∪dopG=K_n , dodajemy do grafu K_n dodatkowy wierzchołek a_{n + 1} i łączymy go q krawędziami z wierzchołkami podgrafu G oraz n-q krawędziami z wierzchołkami grafu dopG, przy czym q należy do przedziału [1, ... ,n] Otrzymujemy wtedy dwa wzajemnie dopełniające się grafy G' i dopG' o n+1 wierzchołkach G'∪dopG'=K_{n + 1} Dodanie wierzchołka a_{n + 1} zwiększa liczbę chromatyczną o 1 przynajmniej dla jednego z grafów G' lub dopG', a zatem χ(G) ≤χ(G) +1 χ(dopG) ≤χ(dopG) +1

Rozważmy przypadek gdy wzrasta tylko jedna liczba chromatyczna. Wówczas sumując obie strony nierówności otrzymujemy χ(G')+χ(dopG')≤χ(G)+χ(dopG)+1≤{z zał.} n+1 +1 ≤n+2

Gdyby nastąpił ewentualny wzrost obydwóch liczb chromatycznych, zauważmy, że musi być wówczas q≥ χ(G) gdyż w przeciwnym razie w grafie G' można by wierzchołkowi a_n+1 przypisać którąkolwiek z nie wykorzystanych barw wierzchołków przyległych do a_n+1. W podobny sposób można jednak wykazać, że musi być n-q≥ χ(dopG). Sumując obie nierówności otrzymamy w tym przypadku: χ(G) + χ(dopG) ≤q+n-q=n, a więc tym bardziej χ(G) + χ(dopG) ≤n+1.

Podnosząc obie strony do kwadratu ( χ(G) + χ(dopG))²≤(n+1)² =>4χ(G)χ(dopG)≤( χ(G) + χ(dopG))²≤(n+1)²

czyli χ(G)χ(dopG )≤ ¼ (n+1)² czyli otrzymaliśmy prawą stronę drugiej nierówności.

(χ(G) +χ(dopG) )²≥4χ(G)χ(dopG) z drugiej nierówności mamy χ(G)χ(dopG) ≥n => 4χ(G)χ(dopG) ≥4n

więc (χ(G) +χ(dopG) )²≥4n pierwiastkujemy stronami χ(G) +χ(dopG)≥2√n czyli otrzymaliśmy lewą stronę pierwszej nierówności.

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

Z tw. Vizinga (∀G) Δ(G)≤χ'(G)≤Δ(G)+1, mamy więc k≤χ'(G)≤k+1. Wystarczy pokazać, że indeks chrom. χ'(G) tego grafu nie jest równy k. k=2 χ'(G)=3 χ'(G)≥k, λ'(G)=k+1. Nie może być χ'(G)=k

Załóżmy, że graf G ma p wierzchołków, każdy o stopniu k>0, przy czym p jest liczbą nieparzystą. Kolorując krawędzie grafu G, żaden kolor nie może wystąpić przy każdym wierzchołku więcej niż raz, więc może być co najwyżej ½ p krawędzi o jednakowym kolorze. Biorąc teraz pod uwagę, że p jest nieparzyste, może być co najwyżej ½ (p-1) krawędzi każdego koloru. Zatem liczba różnych kolorów potrzebnych do pokolorowania krawędzi grafu jest większa bądź równa ( ½ kp)/( ½ (p-1))=kp/(p-1)>k a więc potrzebnych jest więcej niż k kolorów. Zatem potrzeba co najmniej k+1 kolorów.

13. χ(G₁+G₂)=χ(G₁)+χ(G₂)

G₁=(V₁,E₁) G₂=(V₂,E₂) V₁∩V₂=pusty. G₁+G₂ jest grafem (V,E) gdzie V=V₁∪V₂, E=E₁∪E₂∪{(a,b) a∈V₁, b∈V₂}. Graf G₁ kolorujemy χ(G₁) kolorami, graf G₂ χ(G₂) kolorami, ale innymi niż χ(G₁). Otrzymuję pokolorowanie grafu G₁ i G₂ zatem χ(G₁+G₂)≤χ(G₁)+χ(G₂) (*). Zakładam, że χ(G₁+G₂)<χ(G₁)+χ(G₂) to znaczy, że wśród kolorów w G₂ wystąpił przynajmniej jeden kolor, który był wzięty do G₁. Istnieje wierzch. w G₂ u który jest pomalowany na taki sam kolor jak któryś z wierzch. G₁ - ten wierzch. niech będzie v. Z def. grafu u i v są połączone krawędzią, mamy więc sprzeczność bo dwa wierzch. sąsiadujące nie mogą być pomalowane na ten sam kolor. Stąd χ(G₁+G₂) ≥χ(G₁)+χ(G₂) (**). Z (*) i (**) mamy χ(G₁+G₂)=χ(G₁)+χ(G₂).

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

“⇒” Niech G=(V₁,V₂,E) graf dwudzielny ( w którym każda krawędź łączy element należący do V₁ z elementem należącym do V₂). Rozważmy w grafie G cykl v₁,v₂,v₃, ... , v_{n -1} ,v_n,v₁ .Załóżmy że v₁∈V₁. Wówczas istnienie krawędzi v₁v₂ ( z tego że istnieje cykl) z definicji grafu dwudzielnego sprawia że v₂∈V₂; podobnie v₃∈V₁ itd.

Tak więc mamy v₁∈V₁, v₂∈V₂,v₃∈V₁, ... , v_{n -1} ∈V₁ , v_n∈V₂, v₁∈V₁ co implikuje że n parzyste.

“⇐” Jeśli każdy cykl w G jest parzystej długości to wtedy numerując te wierzch. idąc z v₁ do v₂ możemy iść RYS. Wyróżniamy jeden wierzch. i malujemy go na czerwono, pozostałe w odległości jeden malujemy na zielono, następnie na czerwono, itd. Gdyby w którymś kroku trzeba było pomalować dwa sąsiadujące wierzch. na ten sam kolor, to by oznaczało, że w G jest cykl nieparzysty. Zatem sprzeczność, bo zakładaliśmy parzystość cyklu.

15.Niech n=|V|, ∀v degv>(n-1)/2 G ma cykl Hamiltona

Weźmy G-v, ma on cykl Hamiltona i n-1 wierzchołków. RYS1. Ponieważ degv>(n-1)/2 więc istnieją dwa wierzchołki sąsiadujące ze sobą na tym cyklu, v_i, v_i+1 sąsiadujące z v. Gdy mamy już te wierzchołki rozszerzamy cykl o v przez wyrzucenie krawędzi v_iv_i+1 i dodanie krawędzi v_iv i vv_i+1, tak otrzymamy cykl prosty czyli jest to cykl Hamiltona. RYS2

16.Znajdz najmniejsze n takie, że dla każdego grafu o n wierzchołkach |V|=n G ma cykl lub dopG ma cykl.

1,2 - oczywiste, 3-RYS1, 4-RYS2, 5: graf pełny o 5 wierzchołkach ma 10 krawędzi. Załóżmy, że G i dopG nie mają cyklu. W grafie o n wierzchołkach maksymalna ilość krawędzi jaką należy poprowadzić aby nie było żadnego cyklu to n-1.(Tw. Graf o n wierzchołkach i co najmniej n krawędziach zawiera cykl, tzn. |V(G)| ≤|E(G)| to G zawiera cykl) Ponieważ zakładamy, że nie ma cyklu to |E(G)|<|V(G)| czyli |E(G)| ≤|V|-1=4 i |E(dopG)| ≤|V|-1=4. K₅=G+dopG więc |E(K₅)|=|E(G)|+|E(dopG)| ≤8 - sprzeczność bo graf pełny ma 10 krawędzi. Zatem G lub dopG musi mieć cykl. Najmniejsze takie n=5.

17. G=(V,E) i |E|≥(n² -3n+6)/2⇒ G ma cykl Ham.

Załóżmy, że |E(G)|≥ (n² -3n+6)/2 =½(n-1)(n-2)+2=(n-1 nad 2)+2 i usuńmy wierzchołki u i v wraz ze wszystkimi krawędziami wychodzącymi z tych wierzchołków. Ponieważ {u,v}∉E(G), więc usunęliśmy deg(u)+deg(v) krawędzi i 2 wierzchołki. Graf G', który otrzymaliśmy, jest podgrafem K_n-2 grafu K_n, więc |E(K_n-2|=(n-2 nad 2)≥(n-1 nad 2)+2-deg(u)-deg(v). Zatem deg(u)+deg(v)≥(n-1 nad 2)-(n-2 nad 2)+2= ½ (n-1)(n-2)- ½ (n-2)(n-3)+2= ½ (n-2)[(n-1)-(n-3)]+2= ½ (n-2)*2+2=n. Zatem mamy spełnione założenia tw. Ore'a czyli G ma cykl Hamiltona.

18.Udowodnić, że jeśli graf G zawiera cykl Eulera ⇒G zawiera pewien cykl prosty.

Tw: Jeśli graf G zawiera cykl Eulera, to stopień każdego wierzch. jest liczbą parzystą. Dowód: Przypuśćmy, że P jest cyklem Eulera w grafie G. Za każdym razem, gdy cykl P przechodzi przez wierzch., udział krawędzi należących do tego cyklu zwiększa się o 2. Ponieważ każda krawędź występuje w P dokładnie raz, więc stopień każdego wierzch. musi być liczbą parzystą. Lemat: Jeśli w grafie G każdy wierzch. jest stopnia co najmniej 2, to graf G zawiera cykl. Dowód: Załóżmy, że G jest grafem prostym. Niech v będzie dowolnym wierzch. grafu G. Tworzymy trasę vv₁v₂… przez indukcję, wybierając jako v₁ dowolny wierzch. sąsiadujący z v, a następnie, ∀_i>1 wybierając jako wierzch. v_i+1 dowolny wierzch. sąsiadujący z v_i, różny od v_i-1; istnienie takiego wierzch. wynika z założenia o G. Ponieważ G ma skończenie wiele wierzch., więc wreszcie musimy wybrać wierzch. wybrany już wcześniej. Jeśli v_k jest pierwszym takim wierzch., to część trasy znajdująca się między pierwszym i drugim wystąpieniem wierzch. v_k jest szukanym cyklem. Udowodniliśmy że jeśli G zawiera cykl Eulera, to stopień każdego wierzch. jest liczbą parzystą, tzn. 2,4,6,…. Liczby te są ≥2 więc korzystając z lematu wykazaliśmy, że G zawiera cykl prosty.

19a. |E|≥2 ,K(G)≥2⇔[((∀e,f∈E) e∩f≠∅ istnieje cykl prosty taki że e,f∈E(L) ]

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

„⇒”Tw. G dwuspójny ⇔każde dwa wierzch. leżą na pewnym cyklu prostym. Bierzemy dwa wierzch. leżące na cyklu prostym b i c i trzeci wierzch a RYS1 Łączymy wszystkie trzy a, b i c trójkątem wtedy otrzymujemy cykl prosty przechodzący przez dwie sąsiadujące krawędzie l₁ i l₂ RYS2.

„⇐”Skoro każde dwie sąsiednie krawędzie leżą na cyklu prostym więc graf nie ma liści czyli wierzchołków stopnia 1. Zakładam że nie zachodzi K(G)≥2 czyli K(G) <2.Jeśli K(G)=1, czyli istnieje v wierzchołek rozpinający(czyli po wyjęciu wierzch i krawędzi z nim incydentnych rozspójniamy graf).Ale skoro każde dwie krawędzie leżą na cyklu prostym to v również leży na cyklu prostym. Sprzeczność bo aby rozspójnić graf trzeba wyjąć jeszcze co najmniej jeden wierzch czyli K(G)≥2.

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

Ponieważ G jest dwudzielny, więc możemy podzielić jego zbiór wierzchołków na dwa zbiory rozłączne A i B w taki sposób, by każda krawędź grafu G łączyła wierzchołek ze zbioru A z wierzchołkiem ze zbioru B. Niech v₀ v₁…v_mv₀ będzie cyklem w grafie G i załóżmy, że v₀∈A. Wtedy v₁∈B, v₂∈A itd. Ponieważ wierzchołek v_m musi należeć do B, cykl ma długość parzystą.

22. G-spójny, 3-regularny Ham. ⇒ χ'(G)=3

Graf jest spójny ⇔ ∀u,v∈V ∃u-v droga. Graf jest 3-reg. ⇔ z każdego wierzch. wychodzą 3 krawędzie. Ponadto G jest grafem Ham., czyli zawiera cykl Ham.., tzn cykl, który przechodzi przez wszystkie wierzch. w G. Graf jest 3-reg. dla n≥4 i dla n parzystych. (bo dla grafów regularnych |V| * degv = 2 |E|, gdyby |V| nieparzyste i deg=3 to nierówn. nie speł,. bo |E| musi być parzyste). Stąd dla n-nieparzystych i n<4 nie istnieje graf 3-reg.Wracając do naszej konstrukcji kolorujemy krawędzie w cyklu Ham. na przemian 2 kolorami (parzysta liczba wierzch. na pewno się uda). Teraz z każdego wierzch. wychodzi jeszcze po jednej nie pokolorowanej dotychczas krawędzi. Na pewno nie będzie to krawędź łącząca 2 wierzch. sąsiadujące ze sobą w cyklu Ham..(już są pokolorowane). Malujemy te krawędzie trzecim kolorem - otrzymujemy χ'(G)=3. Rysunek - naokoło na okręgu wierzch. będące w cyklu Ham.., a w środku - „trzecie” krawędzie.

24.Czy prawdą jest,że jeśli G=<V,E>, w:ER+ jest „1-1” to G ma dokładnie jedno najtańsze drzewo rozpinające?

(róznowartościowość : ၷ(T')= ၷ(T'') < = > T'=T'' )

Tw. Drzewo T wybrane przez algorytm Kruskala jest najtańszym drzewem rozpinającym w G.

Za pomocą algorytmu Kruskala najtańsze drzewo rozpinające T'=(V,E')_. Zakładamy, że istnieje inne drzewo rozpinające T''=(V,E'') o tej samej wadze czyli ω(T')=ω(T'') ale E'ႹE'' (zaprzeczamy różnowartościowości). Weźmy T'' takie że ma najwięcej krawędzi wspólnych z T'. Niech l najmniejsza liczba taka że e_l∈E'\E'' (bo te drzewa są różne) (czyli e_l jest krawędzią wybraną przez algorytm Kruskala). W T''+e_l istnieje dokładnie jeden cykl C . Istnieje krawędź e∈E(C)\E' , bo w przeciwnym przypadku T' nie było by drzewem, zauważmy że ω(e)>ω(e_l) bo inaczej Algorytm Kruskala w 1-szym kroku wybrałby e bo {e₁,e₂, ... , e_l-1, e} nie tworzą cyklu gdzie {e₁,e₂, ... , e_l-1}∈E'' Jeśli usuniemy krawędź e dostaniemy acykliczny graf T'' - e +e_l gdzie ω( T'' - e +e_l)<ω(T'')=ω(T') czyli sprzeczność z założeniem że T' najtańsze.

26.T drzewo ⇔ ∀T₁,T₂ spójnych podgrafów T zachodzi T₁∩T₂≠∅⇒T₁∩T₂ jest spójnym podgrafem T.

„⇒” T drzewo⇒T spójny. Weźmy dowolne podgrafy spójne T₁ i T₂, rozłączne i dowolne wierzchołki u,v∈V(T₁,T₂). W T₁ ∃u-v droga (ze spójności T₁), w T₂ ∃u-v droga. Każda z tych dróg jest również u-v drogą w G, ale w drzewie ∃ dokładnie jedna u-v droga więc u-v drogi w T₁i T₂ to te same czyli u-v droga jest zawarta w T₁∩T₂. Mamy więc u-v drogę w T₁∩T₂. Rozważone były dowolne wierzchołki u,v więc T₁∩T₂ jest spójny.

„⇐” Nie wprost : T- spójny. Wystarczy wykazać że w T nie ma cykli. Przypuśćmy, że w T jest cykl C. C ma przynajmniej 3 wierzchołki u,v,s. Niech T₁ będzie v-s drogą zawartą w C zawierającą u i niech T₂ będzie v-s drogą zawartą w T nie zawierająca u. rys Grafy T₁ i T₂ są spójne jako drogi i ich częścią wspólną T₁∩T₂ jest zbiór dwóch wierzchołków {v,s}-oczywiście jest to podgraf niespójny grafu T (sprzeczne z zał., że T₁∩T₂ jest podgrafem spójnym). Wniosek : w T nie może być cykli. Czyli T jako graf spójny, acykliczny jest drzewem.

28.T₁,T₂ - drzewa rozpinające G, e∈E(T₁). Udowodnić, że w T₂ istnieje krawędź f t,że T₁-e+f jest drzewem rozpinającym G.

T₁ i T₂ drzewa rozpinające G, Rys1 weźmy e∈E(T₁) po usunięciu krawędzi e z drzewa T₁ mogą wystąpić dwa przypadki: 1) T₁\e aby było rozpinające brakuje jednaj krawędzi dochodzącej do wierzchołka v Rys2 2)T₁\e składa się z dwóch drzew T₁' i T₁''zawierających wszystkie wierzchołki grafu G Rys3. Jeśli e∈E(T₂) to wystarczy przyjąć że e=f . Jeśli e჏E(T₂) to rozważamy dwa powyższe przypadki. Gdy zachodzi (1) to z tego że T₂ rozpinające musi zawierać co najmniej jedną krawędź dochodzącą do wierzchołka v którego nie obejmuje T₁\e, więc biorę taką krawędź z T₂ i dodaję do T₁\e => otrzymuję drzewo rozpinające T₁\e+f (dodanie krawędzi f nie tworzy cyklu bo T₁\e nie miało żadnej krawędzi łączącej z v). Gdy zachodzi (2) , to po wyrzuceniu e otrzymujemy dwa drzewa T₁' i T₁''zawierające wszystkie wierzchołki G, z tego że T₂ rozpinające musi zawierać krawędź f∈E(T₂) łączącą T₁' i T₁'' , bierzemy jedną z takich krawędzi f i otrzymujemy drzewo T₁\e+f rozpinające (bo dodanie f nie tworzy cyklu bo T₁' i T₁'' nie były połączone).

29. Czy prawdą jest,że jeśli diamG=2⇒G ma drzewo rozpinające T t,że diam T=2?

Nie. Kontrprzykład: Weźmy cykl C o długości 5 jest grafem t,że diamG=2. Drzewo rozpinające zawiera wszystkie wierzch. cyklu, ale nie wszystkie krawędzie. Jeśli z naszego grafu wyrzucimy jedną krawędź, to powstanie nam droga prosta P₅. Wiemy, że diamP_n=n-1 (diamP_n - średnica drogi prostej o n wierzchołkach), więc diamP₅=4. Zatem nasza własność nie zachodzi, bo miało wyjść diam=2.

30. a)α₀(G)≥β₁(G), b) α₁(G)≥β₀(G)

a)Weźmy najmniejszy zbiór niezależnych krawędzi S⊆E w grafie G=(V,E) Warunkiem koniecznym istnienia pokrycia T wierzchołkami grafu G jest aby ∀e∈E ∃v∈T. Aby pokryć S⊆E gdzie krawędzie S są niezależne musimy wybrać z każdej krawędzi co najmniej jeden wierzchołek v, a więc α₀(G)≥|S| ⇒ α₀(G)≥β₁(G). b)Ponieważ ∀G α₀(G)+β₀(G)=α₁(G)+β₁(G)=p to z tegi i punktu a) wynika p-β₀(G)≥p-α₁(G)⇔α₁(G)≥β₀(G)

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

b) α₁(G)+β₁(G)=|V|=n

(a) M₀ zawarty w V jeden z największych niezależnych zbiorów wierzchołów niech|M₀|=β₀(G). Ponieważ żadne dwa wierzchołki w M₀ nie są połączone to zbiór V\M₀ liczący n-β₀ wierzchołków tworzy pokrycie wierzchołkowe grafu G dla którego n-β₀(G)≥α₀(G)(*). Jeśli zaś M₁ najmniejsze pokrycie grafu G M₁ zawarty w V taki że |M₁|=α₀(G) to żadna para pozostałych

n-α₀ wierzchołków nie może być połączona krawędzią zatem zbiór V\M₁ jest niezależny z tego wynika że β₀(G)≥n-α₀(G)(**) czyli z (*) i (**) mamy α₀(G)+β₀(G)=n

(b) niech F₁ zawarty w E niezależny i |F₁|=β₁(G). Biorąc pod uwagę sumę zbioru F₁ i zbioru krawędzi grafu G które są przyległe do wierzchołków nie pokrytych przez F₁ otrzymamy pokrycie krawędziowe grafu które oznaczmy F₀ => |F₀| + |F₁|= n a jednocześnie |A₀|≥α₁(G)

α₁(G) + β₁(G) ≤n (*) Z kolei rozważmy najmniejsze pokrycie krawędziowe F₂ grafu G. Z definicji pokrycia wynika że |F₂|=α₁(G) a przy tym F₂ nie może zawierać krawędzi takich że oba przyległe do nich wierzchołki są jednocześnie przyległe do krawędzi zbioru F₁ czyli F₂ jest sumą grafów utworzonych z podzbiorów krawędzi mających co najwyżej jeden wspólny wierzchołek (takie grafy nazywamy gwiazdami) Gwiazda o s krawędziach ma s+1 wierzchołków zatem sumując wierzchołki w poszczególnych gwiazdach otrzymamy liczbą która przekracza liczbę zawartych w nich krawędzi dokładnie o liczbę gwiazd n=|F₂|+|W| gdzie W zbiór gwiazd. Z każdej gwiazdy można wyjąć po jednej krawędzi, a tak otrzymany zbiór krawędzi będzie niezależny z tego wynika że |W|≤β₁(G) czyli n≤α₁(G) + β₁(G) (**) czyli z (*) i (**) mamy

α₁(G)+β₁(G)=n.

32. β₀(G)=χ(dopG)

Kontrprzykład β₀(G)=2 RYS1 dopG to cykl długości nieparzystej χ(dopG)=3 RYS2.

Ale prawdziwa jest nierówność β₀(G)≤ χ(dopG) . β₀(G)=k - największa liczba niezależnych wierzchołków w G, żadne dwa nie są połączone krawędzią .Ale w dopG każde dwa z tych wierzchołków będą połączone czyli na pokolorowanie dopG musimy zużyć co najmniej k kolorów zatem χ(dopG)≥β₀(G).

33. ∀G α₀≥δ(G)

Bierzemy M zawarty w V gdzie |M|=α₀(G) najmniejsza liczba wierzchołków pokrywających wszystkie krawędzie. Bierzemy wierzchołek (jeśli istnieje) v₀჏M => |M|≥N(v₀) gdzie N(v₀) liczba krawędzi wychodzących z v₀ czyli |M|≥deg v₀≥δ(G). Wszystkie wierzchołki nie mogą należeć do M , bo wtedy wszystkie krawędzie pokryte by były dwa razy a szukamy najmniejszego zbioru pokrywającego czyli α₀(G)≥δ(G) .

N(v₀)

34.Dla dowolnego grafu G gdzie |V|=n zachodzi χ(G)β₀(G)≥n.

W prawidłowo pokolorowanym grafie G gdzie liczba chromatyczna χ(G)=k zbiór wierzchołków ulega rozbiciu na rodzinę parami rozłącznych podzbiorów oznakowanych tą samą barwą czyli podzbiorów monochromatycznych :

Żadne dwa wierzchołki u i v należące do tego samego V _χ nie są do siebie wzajemnie przyległe (nie połączone krawędzią) a zatem są to zbiory niezależne czyli | V _χ |≤ β₀(G).

Rozbijamy zbiór wierzchołków V na parami rozłączne podzbiory V₁,V₂, ... , V _{χ (G)} monochromatyczne

Ich liczności wynoszą odpowiednio n₁,n₂, .... ,n_χ(G)

n₁=|V₁|≤β₀(G)

n₂=|V₂|≤β₀(G)

n₃=|V₃|≤β₀(G)

.

.

n _{χ (G)} =|V _{χ (G)} |≤β₀(G)

sumując nierówności stronami otrzymujemy n₁+ n₂+ n₃+ ... + n _{χ (G)} ≤β₀(G)+ β₀(G)+ .... + β₀(G)

czyli n≤ χ(G)β₀(G)

36.G-dwudzielny ⇒ |E|≤α₀β₀ .Ponadto |E|= α₀β₀ G pełny dwudzielny

α₀ - najmniejsza liczność zbioru wierzchołków pokrywających wszystkie krawędzie, β₀ - największa liczność niezależnego zbioru wierzchołków. |E|≤α₀(G)Δ(G) gdzie Δ(G) maksymalny stopień wierzchołka , α₀ ilość wierzchołków która pokrywa wszystkie krawędzie a każdy z wierzchołków może pokryć maksymalnie Δ(G) krawędzi , czyli sumując krawędzie po stopniach wierzchołków z pokrycia otrzymamy |E|= l₁ + l₂ + .... + l_α0 gdzie l_i stopień wierzchołka , skoro nie znamy tych wartość , przyjmując najgorszą możliwość otrzymamy nierówność |E|≤α₀(G)Δ(G)(*) , w grafie dwudzielnym mamy Δ(G)≤β₀(G)(**) bo w klasie wierzchołki są między sobą niezależne i maksymalny stopień grafu G jest nie większy liczbie wierzchołków w liczniejszej klasie a β₀ jest równa liczności wierzchołków w liczniejszej klasie plus ewentualne wierzchołki izolowane z drugiej klasy

( w grafie „normalnym” Δ(G)≤β₀(G) nie jest regułą bo RYS1 ) Czyli z (*) i (**) => |E|≤α₀(G)β₀(G) . Dowód równości: „<=” G graf pełny .RYS2 V=V₁∪V₂ , V₁∩V₂≠∅, |V₁|=l |V₂|=k w grafie pełnym dwudzielnym liczba wszystkich krawędzi wynosi |E|=l*k .Załóżmy że l≤k to α₀= min {l,k}= l (*) . Z Tw. W każdym grafie dwudzielnym G zachodzi β₁(G)=α₀(G) i z Tw Gallai'a: α₀+β₀=|V|=n czyli β₀= |V| - α₀= {z (*) }= |V| - l=k czyli l * k= |E|≤α₀β₀ { z poprzedniej części zadania}=l*k zatem |E|= α₀β₀ „=>” Wiemy że |E|≤α₀Δ(G)≤α₀β₀ a skoro |E|=α₀β₀ to Δ(G)=β₀ k≥Δ(G)=β₀≥k => β₀=k => α₀ + β₀=|V| α₀= |V| - k= l zatem |E|= l*k czyli G dwudzielny pełny .

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

Wyjęcie jednego wierzchołka albo nie zmienia K(G) albo zmniejsza go o jeden. (Z def. spójności - istnieje zbiór S taki, że wyjmując którykolwiek wierzchołek z S Zmniejszamy K(G) o 1). K(G-x)=K(G) albo K(G-x)=K(G)-1. Zatem min K(G-x)=K(G)-1. Więc K(G-x)>=K(G)-1.

39.G spójny ⇔ ∀ podziału V=V₁+V₂; V₁,V₂≠∅, V₁∩V₂=∅ istnieje w G krawędź uv t, że u∈V₁ a v∈V₂
„⇒” Zakładamy, że G spójny. V=V₁∪V₂ .Weźmy v₁∈V₁, ... , v_k∈V₂ to między nimi musi istnieć v₁-v_k droga ( z tego że G spójny) czyli taki ciąg (v₁, ... ,v_k) Zmniejszając wskaźnik k w pewnym momencie dojdziemy do l takiego że v_l∈V₂ pierwszy wierzchołek na naszej drodze z V₂, natomiast v_l-₁ ∈V₁ zatem dla każdego podziału {v_l-1, v_l}∈E gdzie v_l-1 ∈V₁ v_l∈V₂„⇐” (dokładniejsze rozwiązanie u Krzysia Piżamki) Przypuśćmy, że G jest niespójny ⇒ G ma co najmniej 2 składowe. Niech jedną składową będzie V₁ a pozostałe składowe to V₂. Skoro graf jest niespójny więc nie istnieje krawędź łącząca te dwie składowe. Sprzeczność, bo krawędź miała istnieć. Więc graf musi być spójny.

40.(∀G) G- spójny każde dwie najdłuższe drogi proste mają wspólny wierzch.

Zakładam, że nie mają wspólnego wierzchołka. Mamy dwie najdłuższe drogi: P₁ i P₂. Rys. Wybieram na drodze P₁ wierzchołek v₁, a na drodze P₂ wierzchołek u₁. Ponieważ graf ten jest spójny, to istnieje droga P: v₁-u₁. Wierzchołek wspólny drogi P₁ i P oznaczamy v, a wierzchołek wspólny drogi P i P₂ oznaczamy wierzchołkiem u tzn. że pomiędzy wierzchołkiem u i v nie ma żadnego wierzchołka należącego do P₁ lub do P₂. Ponieważ długość drogi między v, u jest >=1, więc istnieje droga v₀-u₀ (gdzie v₀ końcowy wierzchołek drogi P₁, a u₀ drogi P₂). Droga v₀-u₀ jest dłuższa od drogi P₁ i P₂ o co najmniej 1. Otrzymujemy sprzeczność bo drogi P₁ i P₂ miały być najdłuższymi drogami. Zatem każde dwie najdłuższe drogi mają wspólny wierzchołek.

41.Udowodnić, że jeśli |E(G)| ≥ (n-1 nad 2)+1 to G spójny.

Korzystam z tw. 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. Graf jest spójny jeśli k=1. Zatem największa liczba krawędzi w grafie niespójnym może wynosić: |E1|=[(n-1)(n-2)]/2=[n²- 3n +2]/2. Jeśli w grafie G liczba krawędzi jest większa niż |E1|, to G spójny bo każdy graf prosty, który ma n wierzchołków i więcej niż (n-1)(n-2)/2 krawędzi, jest spójny. (n-1 nad 2)+1=[(n-1)!]/[2!(n-3)!] + 1=[(n-1)(n-2)(n-3)!]/2(n-3)! +1=[(n-1)(n-2)]/2 +1.Zatem |E(G)| ≥ [(n-1)(n-2)]/2 +1> [(n-1)(n-2)]/2=|E1|. Czyli E(G)>|E1|. Stąd G spójny.

45.G spójny, |V|≥3 wówczas G² dwuspójny.

Weźmy w G² dwa dowolne nie sąsiadujące wierzchołki u i v. Ponieważ G jest grafem spójnym, więc istnieje między nimi droga. Dla drogi u-v o parzystej długości mamy: [rys1] Między u-v istnieją dwie wewnętrznie rozłączne drogi: P₁ uv₁v₃v i P₂ uv₂v. Dla drogi u-v o nieparzystej długości [rys2]mamy: P₁ uv₁v₃v i P₂ uv₂v₄v. Ogólnie mamy P₁ uv₁v₃...v_2k-1v, P₂ uv₂v₄...v_2kv. Ponieważ dla każdych dwóch nie sąsiednich wierzchołków u i v istnieją w G² dwie wewnętrznie rozłączne drogi czyli K(G²) ≥2 (z tw. Mengera).

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

“⇐” Z lematu, że jeżeli w G stopień każdego wierzchołka≥2 to G zawiera pewien cykl prosty. Mamy dwa wierzchołki, które tworzą cykl. Każde dwa wierzchołki leżą na cyklu prostym. Istnieje cykl C₁ taki, że x,z∈C₁ i istnieje cykl C₂ taki, że y,z∈C₂. Aby dojść z y do x przechodząc przez z należy wyjść z y i iść cyklem C₂ aż do przecięcia się obu cykli, wtedy przechodzimy na cykl C₁ i idziemy do z a następnie do x. Jeżeli na cyklu C₁ najpierw napotkamy x to należy wrócić do punktu przecięcia się cykli i iść w przeciwnym kierunku. Jest to droga prosta bo oba te cykle są proste.

“⇒” przez zaprzeczenie. G nie jest dwuspójny czyli istnieje w G wierzchołek rozcinający. Aby dojść z y do x przez z musimy najpierw przejść z y do x, x do z, a później z z do x. Przechodzimy dwa razy przez wierzchołek x. Nie istnieje droga prosta x-y przechodząca przez z. Sprzeczność.

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

Zbiór rozdzielający S wierzchołki u i v jest to zbiór którego wyjęcie powoduje że wierzchołki u i v znajdą się w różnych składowych grafu G. RYS. Wierzchołki u i v można połączyć drogą bo graf jest spójny. Na pewno co najmniej jeden wierzchołek ze zbioru rozdzielającego musi należeć do tej drogi, gdyż w przeciwnym razie nie dochodziło by do rozspójnienia i podziału na składowe. Załóżmy że wierzchołków na drodze pomiędzy u i v jest n (bez u i v) czyli odległość pomiędzy u i v wynosi n+1 o ile wybraliśmy najkrótszą drogę. Ponieważ maksymalnie można wyjąć wszystkie n wierzchołków wraz z podgrafami połączonymi z nimi więc faktycznie ilość zbiorów u-v rozdzielających jest równa n czyli dist(u,v) -1.

49.G=(V,E) K(G)=k |V|=n ⇒ |E|≥kn/2

Jeśli K(G)=k to każdy wierzchołek grafu ma stopień co najmniej k (z nierówności Whitneya K(G)≤δ(G)).Jeśli jakiś wierzchołek miałby stopień mniejszy od k, to usuwając wszystkie wierzchołki sąsiadujące z nim rozspójniamy graf i to byłoby sprzeczne K(G)=k. Z każdego wierzchołka 1..n wychodzi co najmniej k- krawędzi. Dodając stopnie wierzchołków otrzymujemy podwójną ilość krawędzi. 2|E|=∑_v∈V deg v≥ nk stąd |E|≥nk/2.

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

Jeśli n i p nieparzyste to odpada, bo suma stopni wszystkich wierzchołków musi być parzysta. Warunki konieczne to: 1.0≤n≤p-1 (stopień nie może przekraczać liczby wierzchołków, bo sam ze sobą się nie łączy ). 2. k=np/2 (co najmniej jedna z tych liczb musi być parzysta) Zatem np/2 i n≤p-1⇒∃ G n- regularny stopnia parzystego. p=1 n=0. p=3 n=2. p=5. … p=2k-1 - jeśli weźmiemy cykl prosty o nieparzystej ilości wierzchołków to n=2.W dowolnym cyklu dł. nieparzystej łączymy co drugi wierzchołek, wtedy otrzymamy graf 4-regularny. Następnie w tym samym grafie łączymy co trzeci wierzchołek, wtedy otrzymamy graf 6-regularny i tak dalej łączymy 4,5,...,47. Otrzymamy graf pełny, który też jest stopnia parzystego ponieważ w K_p z każdego wierzchołka wychodzi p-1 krawędzi, czyli dla p- nieparzystego (p-1) parzyste. p - parzyste ⇒stopień wierzchołka w grafie regularnym parzysty lub nieparzysty. Grafy regularne stopni parzystych otrzymujemy tak samo jak dla p- nieparzystych. Grafy regularne o st. nieparzystych przez połączenie wierzchołków naprzeciwko siebie i łącząc wierzchołki cyklu parzystego otrzymamy graf 3-regularny. 5-regularny otrzymamy z 4-regularnego przez połączenie wierzchołków leżących naprzeciwko siebie. 7-regularny otrzymamy z 6-regularnego przez połączenie wierzchołków leżących naprzeciwko siebie. Tak robimy do momentu aż otrzymamy graf pełny, który jest stopnia nieparzystego (tak samo jak w cyklu nieparzystym).

52.W G |V|=6 udow., żeG lub dopG zawiera K₃ Znaleźć min liczbę k taką że dla każdego grafu G o k-wierzch. G lub dog zawiera K₃ (analogicznie zad. 70)

Narysujmy graf G o k=6 wierzch. Połączmy wierzch. linią ciągłą, jeżeli ze sobą sąsiadują w G i przerywaną, jeśli nie sąsiadują w G. Musimy wykazać, że zawsze istnieje trójkąt narysowany linią ciągłą lub trójkąt narysowany linią przerywaną. Niech v będzie dowolnym wierzch.. Wtedy musi istnieć dokładnie pięć krawędzi incydentnych z v, ciągłych lub przerywanych, a więc co najmniej trzy z nich muszą być tego samego typu. Przypuśćmy, że istnieją trzy ciągłe krawędzie. RYS1. Jeśli wierzch. w i x sąsiadują ze sobą w G, to wierzch. v, w i x tworzą trójkąt narysowany linią ciągłą, co zakończy dowód. Podobnie, jeśli wierzch. w i y lub wierzch. x i y sąsiadują w G, to znów otrzymamy trójkąt narysowany linią ciągłą. RYS2. Wreszcie, jeśli żadne dwa wierzch. w, x i y nie sąsiadują w G, to wierzch. w, x i y tworzą trójkąt narysowany linią przerywaną RYS3, co kończy dowód.

54. K(G) ≤λ(G) ≤δ(G)

Aby udowodnić pierwszą nierówność, trzeba rozważyć kilka możliwych przypadków. Jeśli G niespójny lub jednowierzchołkowy mamy K(G)= ၬ(G)=0 czyli spełnione. Jeśli G minimalnie spójny krawędziowo (czyli spójny graf zawierający most) czyli ၬ(G)=1 bo po wyjęciu mostu rozspójniamy graf ale wtedy k(g)=1 bo zawiera wierzchołek przyległy do krawędzi będącej mostem ,jego wyjęcie rozspójnia graf. Niech więc ၬ(G)≥1 czyli graf zawiera nie mniej niż dwuelementowy zbiór krawędzi których usunięcie rozspójnia graf.

Jeśli usuniemy ၬ(G) -1 krawędzi otrzymamy spójny graf z mostem który oznaczamy l_{i j} .Dla każdej z usuniętych ၬ(G) - 1 krawędzi wybieramy dowolny przyległy do niej wierzchołek ale różny od a_i i a_j .Usunięcie wszystkich tak oznaczonych wierzchołków spowoduje też usunięcie nie mniej niż ၬ(G) -1 krawędzi .Jeśli otrzymamy wtedy graf niespójny to K(G)< ၬ(G), jeśli dalej jest spójny to zawiera most l_{i j} a to oznacza że usunięcie wierzchołka a_i lub a_j rozspójnia graf .W każdym jednak przypadku mamy K(G) Ⴃၬ(G)

Drugą nierówność łatwo można uzasadnić biorąc pod uwagę, że jeśli graf G nie zawiera krawędzi to ၬ(G)=0 , zaś jeśli ၬ(G)>0 to G staje się niespójny po usunięciu wszystkich krawędzi przyległych do wierzchołka o najniższym stopniu a zatem w obu przypadkach mamy ၬ(G) Ⴃၤ(G).

56. Dla jakich n można obejść konikiem szachownicę nxn tak, aby wrócić do początku i nie być 2 razy w tym samym miejscu.

Potraktujemy kwadrat szachownicy jako wierzch. grafu, przy czym dwa z nich połączymy krawędzią, jeżeli jest możliwy ruch skoczka z jednego pola na drugie. Wtedy znalezienie trasy dla skoczka jest równoznaczne ze znalezieniem cyklu Ham.. Dla n- nieparzystego każdy cykl wykonany konikiem jest parzystej długości, czyli nie ma cyklu przechodzącego przez wszystkie wierzch.. Dla n- parzystego i n=2 nie możliwe są żadne ruchy, ale już dla n>2 i n- parzystego da się.

57. V={a₁,...,a_k} a_i ∈{0,1}} w₁,v₁∈E jeśli różnią się na dokładnie jednym miejscu udowodnić, że Q_k jest regularny oraz znaleźć liczbę krawędzi, wierzch..

Q_k=<V,E>; V={a₁,...,a_k} a ∈{0,1}} Takich ciągów istnieje 2^k. Jeśli v₁,v₂∈E to muszą różnić się na dokładnie jednym miejscu. V v_i=a₁,..a_k v_j=b₁,...b_k istnieje n t,że a_n≠b_n to każdy wierzch. v_i jest indukowany k krawędziami to G- k-regularny. Ilość wierzch. w tym zbiorze wynosi 2^k, zatem ilość krawędzi w tym zbiorze wynosi (k*2^k)/2

58. Niech M będzie prostokątem łacińskim wymiaru m × n, w którym m<n. Wtedy prostokąt M można rozszerzyć do kwadratu łacińskiego dopisując n-m nowych wierszy.

Pokażemy, że prostokąt M można rozszerzyć do prostokąta łacińskiego wymiaru (m+1)na n. Powtarzając to postępowanie otrzymamy w końcu kwadrat łaciński. Niech E={1,2,...,n} i niech S=(S₁,...,S_n), gdzie S_i jest zbiorem tych liczb należących do E, które nie występują w i-tej kolumnie prostokąta M. Z tw. Halla wynika, że wystarczy sprawdzić, czy suma dowolnych k zbiorów S_i ma co najmniej k elementów. Ale to jest oczywiste, gdyż taka suma zawiera (n-m)*k elementów, wliczając powtórzenia, a gdyby zawierała mniej niż k różnych elementów, to co najmniej jeden z nich musiałby powtórzyć się więcej niż n-m razy. Ponieważ każdy element występuje dokładnie n-m razy, więc mamy

oczekiwaną sprzeczność. Zatem w S istnieje zbiór k różnych elementów zbioru E zawierający po jednym elemencie z każdego S_i.

59.G ≅ dopG ⇒|v|=4k, lub |v|=4k+1

Aby graf G był izomorficzny ze swoim dopełnieniem, to oba grafy muszą mieć tę samą ilość wierzch. i krawędzi. Ale ilość krawędzi w grafie pełnym wynosi n(n-1)/2, czyli |E(G)|+|E(dopG)| =n(n-1)/2. Zatem n(n-1) musi być liczbą parzystą, więc n(n-1)/2=2k to n(n-1)=4k (L strona musi być podzielna przez 4) wobec tego n=4k lub n=4k+1

60. G lub dopG jest spójny.

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ę.

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.

Niech będzie n Arabów i niech ma miejsce jakieś powitanie. Wówczas każda osoba uściśnie od 0 do n-1 dłoni. Weźmy szufladki oznaczone liczbami od 0 do n-1 i niech każda osoba, po napisaniu na kartce papieru swojego nazwiska, umieści ją w szufladce odpowiadającej liczbie wykonanych przez nią uścisków. Aby pokazać, że dwie osoby ściskały tę samą liczbę dłoni, wykażemy, że jedna z szufladek zawiera więcej niż jedną kartkę. Jest n kartek wpadających do n szufladek, a więc stosując tylko zasadę szufladkową, nie możemy być pewni, że tak się stanie. Wszystko byłoby w porządku, chyba że do każdej szufladki wpadnie dokładnie jedna kartka. Lecz gdyby tak było, to kartka szejka znienawidzonego byłaby w szufladce oznakowanej przez 0, a szejka uwielbianego w szufladce oznakowanej przez n-1. Oznacza to, że znienawidzony nie przywitał się z żadnym innym szejkiem, a uwielbiany podał rękę każdemu (łącznie z znienawidzonym), co jest oczywiście niemożliwe.

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.

Podzielmy tarczę na 7 części. RYS. Jeżeli 7 punktów jest umieszczonych na tarczy w ten sposób, że żadne dwa punkty nie są w odległości mniejszej niż 1, to wówczas żadne dwa punkty nie mogą być w jednej części. W ten sposób, w każdej części będzie znajdował się jeden punkt. Oznacza to, że jeden punkt będzie w środku, a pozostałe na obwodzie. Każda sąsiednia para punktów leżących na obwodzie musi tworzyć łuk pod kątem 60° lub więcej, a ponieważ tych sześć kątów musi dać w sumie 360°, wynika stąd, że każdy z nich wynosi dokładnie 60°.

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

Niech a₁, …, a_n będą dowolnymi dodatnimi liczbami całkowitymi. Rozważmy n szufladek. Umieśćmy w szufladkach n podzbiorów {a₁}, {a₁,a₂}, …, {a₁,a₂,…,a_n} ze względu na resztę z dzielenia sumy elementów podzbioru przez n. Jeżeli którykolwiek z tych podzbiorów będzie w szufladce 0, to suma elementów tego zbioru dzieli się przez n. Jeżeli jednak taka sytuacja nie zachodzi, wtedy n zbiorów będzie rozmieszczonych w pozostałych n-1 szufladkach. W ten sposób, na mocy zasady szufladkowej, dwa z nich będą w tej samej szufladce. Ponieważ dają tę samą resztę z dzielenia przez n, wynika stąd, że ich różnica jest podzielna przez n.

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

Przypomnijmy, że z lematu o uściskach dłoni, dla dowolnego grafu G=(V,E) ∑δv=2|E| (δ-stopień wierzchołka), co jest parzyste. Tak więc ∑δv(nieparzyste) + ∑δv(parzyste) = 2|E|(parzyste). Stąd wynika, że suma stopni nieparzystych jest parzysta, czyli musi ich być parzysta liczba.

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

Niech G=(V₁,E,V₂) będzie grafem dwudzielnym (w którym zbiór wierzchołków jest podzielony na V₁ i V₂, a każda krawędź łączy element należący do V₁ z elementem należącym do V₂). Rozważmy w grafie G cykl v₁,v₂,v₃,…,v_n-1,v_n,v₁. Załóżmy np. że v₁∈V₁ itd. Wówczas istnienie krawędzi v₁v₂ zapewnia, że v₂∈V₂: podobnie v₃∈V₁ itd. Tak więc mamy v₁∈V₁, v₂∈V₂, v₃∈V₁,…, v_n-1∈V₁, v_n∈V₂, v₁∈V₁ co oczywiście implikuje, że n jest parzyste.

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.

Potraktujemy kwadrat szachownicy jako wierzchołki grafu, przy czym dwa z nich połączymy krawędzią, jeżeli jest możliwy ruch skoczka z jednego pola na drugie. Wtedy znalezienie trasy dla skoczka jest równoważne ze znalezieniem cyklu Hamiltona.

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.

Załóżmy, że graf G ma n wierzchołków, każdy o stopniu d>0, przy czym n jest liczbą nieparzystą. Kolorując krawędzie grafu G, żaden kolor nie może wystąpić przy każdym wierzchołku więcej niż raz, więc może być co najwyżej ½ n krawędzi o jednakowym kolorze. Biorąc teraz pod uwagę, że n jest nieparzyste, może być co najwyżej ½ (n-1) krawędzi każdego koloru. Zatem liczba różnych kolorów potrzebnych do pokolorowania krawędzi grafu jest większa bądź równa ( ½ dn)/( ½ (n-1))=dn/(n-1)>d a więc potrzebnych jest więcej niż 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.

Narysujmy graf, w którym wierzchołki będą reprezentować osoby i dwa wierzchołki będą połączone linią ciągłą, jeśli odpowiednie osoby znają się, a linią przerywaną, jeśli się nie znają. Musimy wykazać, że zawsze istnieje trójkąt narysowany linią ciągłą lub trójkąt narysowany linią przerywaną. Niech v będzie dowolnym wierzchołkiem. Wtedy musi istnieć dokładnie pięć krawędzi incydentnych z v, ciągłych lub przerywanych, a więc co najmniej trzy z nich muszą być tego samego typu. Przypuśćmy, że istnieją trzy ciągłe krawędzie. RYS1. Jeśli osoby odpowiadające wierzchołkom w i x znają się, to wierzchołki v, w i x tworzą trójkąt narysowany linią ciągłą, co zakończy dowód. Podobnie, jeśli osoby odpowiadające wierzchołkom w i y lub wierzchołkom x i y znają się, to znów otrzymamy trójkąt narysowany linią ciągłą. RYS2. Wreszcie, jeśli żadne dwie osoby odpowiadające wierzchołkom w, x i y nie znają się, to wierzchołki w, x i y tworzą trójkąt narysowany linią przerywaną RYS3, co kończy dowód.

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

Ponieważ G jest dwudzielny, więc możemy podzielić jego zbiór wierzchołków na dwa zbiory rozłączne A i B w taki sposób, by każda krawędź grafu G łączyła wierzchołek ze zbioru A z wierzchołkiem ze zbioru B. Niech v₀ v₁…v_mv₀ będzie cyklem w grafie G i załóżmy, że v₀∈A. Wtedy v₁∈B, v₂∈A itd. Ponieważ wierzchołek v_m musi należeć do B, cykl 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.

Jeśli graf G ma pętle lub krawędzie wielokrotne, to lemat jest trywialny. Możemy zatem założyć, że G jest grafem prostym. Niech v będzie dowolnym wierzchołkiem grafu G. Tworzymy trasę vv₁v₂… przez indukcję, wybierając jako v₁ dowolny wierzchołek sąsiadujący z v, a następnie, ∀_i>1 wybierając jako wierzchołek v_i+1 dowolny wierzchołek sąsiadujący z v_i, różny od v_i-1; istnienie takiego wierzchołka wynika z założenia o G. Ponieważ G ma skończenie wiele wierzchołków, więc wreszcie musimy wybrać wierzchołek wybrany już wcześniej. Jeśli v_k jest pierwszym takim wierzchołkiem, to część trasy znajdująca się między pierwszym i drugim wystąpieniem wierzchołka v_k jest szukanym cyklem.

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

Każdemu drzewu oznakowanemu mającemu n wierzchołków odpowiada dokładnie jedno drzewo spinające grafu K_n. Odwrotnie, z każdego drzewa spinającego grafu K_n można utworzyć dokładnie jedno drzewo oznakowane mające n wierzchołków.

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).

Ten graf jest grafem spójnym mającym n+(2n+1)+1+1=3n+3 wierzchołków i [4n+(2n+1)+2+1]/2=3n+2 krawędzi, a więc jest drzewem na mocy twierdzenia: T jest grafem spójnym i ma n-1 krawędzi, gdzie T- graf o n wierzchołkach.

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.

Udowodnimy prawdziwość dolnego ograniczenia m≥n-k przez indukcję względem liczby krawędzi grafu G. Dla grafu pustego ta nierówność jest trywialna. Jeśli graf G ma najmniejszą możliwą ilość krawędzi (powiedzmy m0), to usunięcie którejkolwiek krawędzi powoduje zwiększenie liczby składowych o 1 i powstały w ten sposób graf ma n wierzchołków, k+1 składowych oraz m0-1 krawędzi. Z założenia indukcyjnego wynika, że m0-1≥n-(k+1), skąd otrzymujemy m0≥n-k, cnd. Aby dowieść ograniczenia górnego, możemy założyć, że każda składowa grafu G jest grafem pełnym. Przypuśćmy zatem, że istnieją dwie składowe Ci i Cj mające odpowiednio ni i nj wierzchołków, przy czym ni≥nj≥1. Jeśli zastąpimy składowe Ci oraz Cj grafami pełnymi mającymi odpowiednio ni+1 i nj-1 wierzchołków, to całkowita liczba wierzchołków nie zmieni się, a liczba krawędzi zmieni się o wielkość: [((ni+1)ni-ni(ni-1)/2]-[(nj(nj-1)-(nj-1)(nj-2)/2]=ni-nj+1, która jest liczbą dodatnią. Wynika stąd, że aby graf G miał maksymalną liczbę krawędzi, musi składać się z grafu pełnego mającego n-k+1 wierzchołków i z k-1 wierzchołków izolowanych. Stąd wynika teza twierdzenia. Wniosek: Każdy graf prosty, który ma n wierzchołków i więcej niż (n-1)(n-2)/2 krawędzi jest spójny.

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)?

Drogi istnieją tylko wtedy, kiedy n=1,2 lub 3 (chociaż dla pierwszych dwóch przypadków żadne ruchy nie są możliwe!).Rys1. Dla n≥4 graf otrzymany na podstawie ruchów skoczka nie jest eulerowski, ponieważ ma osiem wierzchołków nieparzystego wierzchołka (Tw. G jest eulerowski każdy wierzchołek w G ma stopień parzysty); np.RYS2

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

Najmniejszym przykładem jest cykl na 5 wierzchołkach.

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?

Wystarczy użyć dwóch kolorów. Niech będzie to kolory biały i czarny. Przyjmujemy, że kartka ma kolor biały. Na ten kolor malujemy również przecięcia 2,4,6,8,... okręgów. Na czarno malujemy przecięcia 1,3,5,7,9,… okręgów. Zrób rysunek i będzie widać!

79.Indeks chromatyczny Kn wynosi : χ'(K_n)=n-1 dla n parzystych i χ'(K_n)=n dla n nieparzystych.Każdy wierzchołek grafu K_n ma stopień n-1. W przypadku gdy n jest nieparzyste, potrzeba więcej niż n-1 kolorów do pokolorowania krawędzi tego grafu. Pokażemy, że w tym przypadku χ'(K_n)=n, opisując sposób kolorowania krawędzi grafu K_n za pomocą n kolorów. Załóżmy, że n wierzchołków tworzy prawidłowy wielobok o n bokach i narysujemy każdą krawędź jako linię prostą. Następnie pokolorujemy dwie krawędzie tym samym kolorem są one równoległe. (Tak otrzymane kolorowanie w przypadku n=5 i n=7 są na rysunku.). Dla n nieparzystego taka metoda da w efekcie pokolorowanie krawędzi grafu K_n za pomocą n kolorów. Jest jasne, że zostało użytych n kolorów, że żadne dwie krawędzie tego samego koloru nie spotykają się oraz że wszystkie ½ n(n-1) krawędzi zostały pokolorowane (każdy kolor użyto dla dokładnie ½ (n-1) krawędzi). Wykazaliśmy w ten sposób rezultat dla n nieparzystego. Niech teraz n będzie parzyste i pokolorujemy krawędzie grafu K_n-1 za pomocą n-1 kolorów w sposób opisany powyżej. Zauważymy, że w tym kolorowaniu, przy każdym wierzchołku brakuje jednego koloru, a ponadto każdy z n-1 kolorów jest brakującym przy dokładnie jednym z wierzchołków. Dodajmy n-ty wierzchołek i połączmy go krawędzią po kolei z każdym z n-1 pozostałych wierzchołków. Pokolorujemy te krawędzie, używając każdorazowo brakującego przy danym wierzchołku koloru. Łatwo można zauważyć, że w wyniku takiego postępowania otrzymamy pokolorowanie krawędzi grafu K_n za pomocą n-1 kolorów: przypadek n=8 pokazano na rysunku.

80.Niech (V₁,V₂,E) będzie grafem dwudzielnym o max stopniu wierzchołka = d. Wówczas χ'(G)=d.Zastosujemy metodę indukcji względem |E|. Załóżmy, że G ma |E|>0, jego największy stopień wierzchołka wynosi d oraz że teza twierdzenia jest prawdziwa dla grafów dwudzielnych o liczbie krawędzi mniejszej niż |E|. Usuńmy z G pewną krawędź vw, otrzymując nowy graf dwudzielny G'. Największy stopień wierzchołka w G' jest równy co najwyżej d, a więc na mocy założenia indukcyjnego, możemy pokolorować krawędzie grafu G' za pomocą d kolorów: wykonajmy jedno z takich kolorowań. Jeżeli przy obu wierzchołkach v i w brakuje jednego z d kolorów, to ten właśnie kolor może być użyty do pomalowania krawędzi vw, dając żądane kolorowanie grafu G za pomocą d kolorów. Załóżmy na odwrót, że do pokolorowania krawędzi wychodzących z wierzchołków v i w użyliśmy wszystkich kolorów. Ponieważ w G' stopnie wierzchołków v iw są równe co najwyżej d-1, zatem istnieje kolor, powiedzmy c, którego brakuje przy v (a więc jest on użyty przy w) oraz istnieje inny kolor, powiedzmy c', którego brakuje przy w (a więc jest on użyty przy v). Rozważmy teraz podgraf grafu G' utworzony przez krawędzie koloru c lub c' i w szczególności weźmy pod uwagę tę składową tego podgrafu, która zawiera wierzchołek v (należący, powiedzmy do V₁). Składowa ta jest drogą o początku w v∈V₁ i krawędziach pokolorowanych kolejno kolorami c', c, c',…. Droga ta nie może kończyć się w wierzchołku w∈V₂; gdyby tak było, to miałaby ona nieparzystą liczbę krawędzi, czyli kończyłaby się krawędzią o kolorze c', a przecież dla żadnej z takich krawędzi wierzchołek w nie jest wierzchołkiem końcowym. Teraz możemy w tej składowej zamienić między sobą dwa kolory, otrzymując w dalszym ciągu kolorowanie krawędzi grafu G' za pomocą d kolorów: np. RYS. Zamieniając kolory, odnosimy następującą korzyść: tym razem brakuje koloru c' przy obu wierzchołkach v i w, możemy zatem pomalować tym kolorem krawędź vw, otrzymując żądane kolorowanie grafu G d kolorami.

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.

Indukcja względem |E|. Załóżmy, że |E|>0 i że teza jest prawdziwa dla grafów o mniejszej liczbie krawędzi. Niech v∈V ma dodatni stopień i niech będzie on wierzchołkiem końcowym dokładnie r krawędzi e₁=vv₁,…,e_r=vv_r. Niech G' będzie grafem (V,E\{e₁,…,e_r}). Wówczas największy stopień wierzchołka w G' jest równy co najwyżej d i, na mocy założenia indukcyjnego, krawędzie grafu G' mogą być pokolorowane za pomocą d+1 kolorów: wykonajmy takie pokolorowanie. W G' stopień każdego z wierzchołków v₁,…,v_r jest ≤d-1, a mamy do dyspozycji d+1 kolorów. W ten sposób dla każdego wierzchołka vi istnieją co najmniej dwa kolory, które przy nim nie występują, a więc nie występują one również przy obu wierzchołkach końcowych krawędzi e_i. W szczególności jest jeden taki kolor dla krawędzi e₁ oraz dwa kolory dla każdej z pozostałych krawędzi. Zatem istnieje sposób pokolorowania krawędzi całego grafu G za pomocą d+1 kolorów, co kończ dowód.

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

Przypuśćmy, że u i v są wierzchołkami stopni nieparzystych. Utwórzmy nową krawędź e, łączącą je. Wtedy graf G∪{e} ma wszystkie wierzchołki stopni parzystych, a więc ma cykl Eulera bo graf spójny, w którym każdy wierzchołek ma stopień parzysty ma cykl Eulera. Usuńmy znowu krawędź e. To, co pozostanie z cylku Eulera, jest drogą Eulera w grafie G.

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

Indukcja względem liczby wierzchołków grafu G. Niech G będzie grafem prostym mającym n wierzchołków. Jeśli usuniemy z niego dowolny wierzchołek v wraz z krawędziami incydentnymi z nim, to otrzymany graf będzie również grafem prostym, który będzie miał n-1 wierzchołków oraz największy stopień wierzchołka będzie nie większy niż Δ. RYS. Z założenia indukcyjnego wynika, że liczba chromatyczna tego grafu jest równa Δ+1. Wtedy χ(G)=Δ+1 otrzymamy nadając wierzchołkowi v kolor inny niż kolory wierzchołków sąsiadujących z v.

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

Załóżmy, że nasz graf jest spójny i ma co najmniej 3 wierzchołki. Gdyby każdy wierzchołek miał stopień co najmniej 6, to 6n≤2m, a więc 3n≤m ale m≤3n-6 więc 3n≤3n-6, co jest niemożliwe.

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

Indukcja ze względu na liczbę wierzchołków. Przypuśćmy, że G jest planarnym grafem prostym mającym n wierzchołków i że wszystkie planarne grafy proste mające n-1 wierzchołków są 6 - kolorowalne. G ma wierzchołek v stopnia co najwyżej 5. Jeśli usuniemy wierzchołek v wraz z wszystkimi krawędziami z nim incydentnymi, to otrzymany graf będzie miał n-1 wierzchołków, a więc będzie 6 - kolorowalny. RYS. Wtedy 6 - kolorowanie grafu G otrzymujemy, kolorując wierzchołek v kolorem różnym od kolorów wierzchołków sąsiadujących.

86. Wzór Eulera. Niech G=(V,E) będzie spójnym grafem planarnym. Wówczas w dowolnej planarnej reprezentacji grafu G liczba regionów jest równa f=|E|-|V|+2.

Indukcja względem liczby cykli zawartych w G. Jeżeli graf nie zawiera cykli, to jest on drzewem i jest oczywiste, że każda jego planarna reprezentacja będzie miała dokładnie jeden region. Wiem, że dla drzewa |E|=|V|-1, czyli w tym przypadku f(G)=|E|-|V|+2=|V|-1-|V|+2=1 jak żądaliśmy. Załóżmy więc, że graf planarny G ma co najmniej jeden cykl i że wynik jest prawdziwy dla grafów o mniejszej liczbie cykli. Rozważmy planarną reprezentację grafu G. Niech e będzie krawędzią w G, należącą do jednego z tych cykli. Niech G' będzie grafem otrzymanym z G poprzez usunięcie krawędzie e. Wówczas usunięcie e z danej planarnej reprezentacji grafu G daje planarną reprezentację grafu G'. Ponadto G' jest spójny i ma mniej cykli niż G. Możemy więc zastosować założenie indukcyjne otrzymując f(G')=|E-{e}|-|V|+2=|E|-|V|+1. Ponieważ e była częścią cyklu, jej wstawienie podzieli jakiś region w reprezentacji grafu G' na dwa regiony. W ten sposób dana planarna reprezentacja grafu G rzeczywiście ma |E|-|V|+2 regiony.

87. Niech G=(V,E) będzie planarnym grafem o k składowych. Wówczas w dowolnej planarnej reprezentacji grafu G liczba regionów f=|E|-|V|+k+1.

Gdy mamy daną dowolną reprezentację grafu G, wówczas dodanie pewnych k-1 krawędzi połączy składowe i da w efekcie planarną reprezentację spójnego grafu planarnego G'=(V,E') z taką samą liczbą regionów jak poprzednio. Na podstawie wzoru Eulera liczba regionów w planarnej reprezentacji grafu G' wynosi: |E'|-|V|+2=(|E|+k-1)-|V|+2=|E|-|V|+k+1.

88. Jeżeli G=(V,E) jest grafem planarnym, takim, że |V|≥3, to |E|≤3|V|-6.

Załóżmy, że G jest spójny. Niech f będzie liczbą regionów w planarnej reprezentacji grafu G. Założenie |V|≥3 gwarantuje, że każdy region jest ograniczony przez co najmniej 3 krawędzie, a więc ogólna liczba krawędzi tworzących granice jest równa co najmniej 3f. Ale ogólna liczba krawędzi tworzących granice jest równa dokładnie 2|E| (gdyż każda krawędź jest liczona tutaj dwukrotnie). W ten sposób 2|E|≥3f=3(|E|-|V|+2) czyli |E|≤3|V|-6.

89. Jeżeli G=(V,E) jest planarnym grafem dwudzielnym, takim że |V|≥3, to |E|≤2|V|-4.

Graf dwudzielny nie ma cykli składających się z nieparzystej liczby krawędzi: wynika stąd, że granica każdego regionu w planarnej reprezentacji grafu dwudzielnego musi składać się z parzystej liczby krawędzi. W ten sposób żadna granica nie ma dokładnie 3 krawędzi. Zatem granica każdego regionu składa się z co najmniej 4 krawędzi. Ale ogólna liczba krawędzi tworzących granice jest równa dokładnie 2|E| (gdyż każda krawędź jest liczona tutaj dwukrotnie). W ten sposób 2|E|≥3f=4(|E|-|V|+2) czyli |E|≤2|V|-4.

90. Niech G=(V,E) będzie grafem planarnym, zawierającym cykl i, w którym liczba krawędzi w najkrótszym cyklu jest równa r (obwód grafu G). Wówczas (r-2)|E|≤r(|V|-2).

W jakiejkolwiek planarnej reprezentacji grafu G każdy region ma granicę złożoną z co najmniej r krawędzi. . Ale ogólna liczba krawędzi tworzących granice jest równa dokładnie 2|E| (gdyż każda krawędź jest liczona tutaj dwukrotnie). W ten sposób 2|E|≥rf=r(|E|-|V|+2) czyli (r-2)|E|≤r(|V|-2).

91. Niech G będzie spójnym grafem planarnym, w którym każdy wierzchołek ma dodatni stopień d i dla którego, w pewnej planarnej reprezentacji, każdy region jest ograniczony c krawędziami. Pokazać, że 1/c +1/d >1/2 . Wypisać wszystkie pary liczb całkowitych c,d≥3, które spełniają tę nierówność i każdym przypadku wyznaczyć opisany wyżej graf G.

Niech f będzie liczbą regionów. Wówczas f=|E|-|V|+2 i 2|E|=cf=d|V|. Dzielimy pierwszą równość przez 2|E| i podstawiamy za 2|E| cf. Wtedy otrzymujemy f/cf+|V|/cf=1/2+2/cf ⇔1/c+|V|/cf=1/2+2/cf. Zamiast cf podstawiamy teraz dv: 1/c+|V|/d|V|=1/2+2/d|V| ⇔1/c+1/d=1/2 + 2/d|V|, d>0 i |V|>0 ⇒2/d|V|>0 czyli 1/c+1/d>1/2.

(c,d) może być (3,3), (3,4), (4,3), (3,5), (5,3) czyli kolejno czworościan, ośmiościan, sześcian, dwudziestościan i dwunastościan.

---