1. Każdy pięciospójny graf planarny ma co najmniej 12 wierzchołków
Graf pięciospójny ma wszystkie wierzchołki stopnia co najmniej piątego. Zatem |V|5/2≤|E| (liczba krawędzi). W grafie planarnym |E|≤3|V|-6 5|V|/2≤|E|≤3|V|-6 5|V|/2≤3*|V|-6 (5|V|-6|V|)/2≤ (-6) -|V|/2≤ (-6) |V|≥12. Załóżmy, że istnieje wierzchołek stopnia mniejszego od 5, np. 4. Wyciągnięcie 4 sąsiadujących wierzchołków z tym jednym wyróżnionym rozspójnia graf, a graf miał być pięciospójny, więc mamy sprzeczność.
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
Dowód wniosku: W jakiejkolwiek planarnej reprezentacji grafu G każdy region ma granicę złożoną z co najmniej r krawędzi. W ten sposób 2|E|≥r(|E|-|V|+2), gdzie (|E|-|V|+2)=f-region.
3. Nie istnieje graf planarny o 5 regionach taki, że każde dwa mają wspólną krawędź
Niech istnieje graf o f=5. W każdym obszarze (regionie) postawimy kropkę. Ponieważ istnieje krawędź wspólna dla każdych dwóch obszarów to można przejść z obszaru do obszaru po krawędzi łączącej dwa wierzchołki leżące na wybranych regionach. Dana krawędź nie będzie przechodzić przez żaden inny obszar gdyż istniała krawędź rozgraniczająca te dwa obszary. W rezultacie dostaniemy graf K5, który nie jest planarny. Czyli sprzeczność. RYS
4. Uzasadnić, że K3,3 i k5 nie są planarne
K5: 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 wierzchołkach |V|=5 i |E|=10. Tak więc 10≤9 co jest nieprawdą. Zatem doszliśmy do sprzeczności, a stąd wynika, że K5 nie jest planarny.
K3,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 K3,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) ≤4. 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 degGv≤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 (v1,v2,v3,v4). Niech Gij - graf indukowany przez f-1({ci,cj}) przez wierzchołki pomalowane na kolor ci lub cj. Rozważmy G1,3. Jeżeli v1 i v3 leżą w różnych składowych grafu to w jednej z tych składowych zamienimy kolory i tak, np. wierzchołek v1 malujemy kolorem c3, v można pomalować na kolor c1. Jeśli v1 i v3 leżą w tych samych składowych to v2 i v4 leżą w różnych składowych grafu G2,4. W G1,3 istnieje droga v1-v3 złożona z c1 i c3 kolorów. RYS2. Jeżeli jest wierzchołek 4 to sprzeczność bo nie może on być jednocześnie pomalowany na c1 lub c3 i pomalowany na c2 lub c4. G2,4 rozpatrujemy w ten sam sposób jak G1,3.
6. Graf planarny może być umieszczony na powierzchni kuli
“<=” Niech G będzie grafem umieszczonym na powierzchni kuli. Umieszczamy kulę na płaszczyźnie tak, aby biegun północny N był rozłączny z G. Wówczas wymaganą płaską reprezentację otrzymamy poprzez rzut skrajny łączący N. RYS.“ ⇒” Graf planarny wkładamy w sferę. Dzieli on tę sferę na regiony, które są skończone z wyjątkiem regionu, który odwzorowuje płaszczyznę na region zawierający biegun północny kuli N.
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 dopG jest grafem planarnym. Z tw. Eulera mamy |E|≤3|V|-6 |E(G)|= |V|(|V|-1)/2 - |E(dopG)| ≥ |V|(|V|-1)/2 + 6-3|V|≥3|V|+6 |V|2-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)
Dowód 1: Zakładam, że G kolorujemy n=χ(G) kolorami czyli mamy n niezależnych podzbiorów wierzchołków p1,…,pn. |p1|+|p2|+…+|pn|. Co najmniej jeden z tych podzbiorów ma liczność |pi|≥p/n. Wszystkich wierzchołków w G jest co najmniej tyle co w p1, dodając te dołączone spoza tego zbioru jest ich k bo G jest k - regularny. P≥ (p/n)+k p-k≥p/n n(p-k) ≥p n≥p/(p-k) χ(G)=n wystarczy użyć tylu kolorów χ(G)=n≥p/(p-k) χ(G) ≥p/(p-k)
Dowód 2: Jeśli ci jest liczbą wierzchołków pokolorowanych kolorem i dla 1≤i≤χ(G), to ci≤p-k. Zatem p=c1+c2+…+cp≤χ(G)(p-k), a więc χ(G)≥p/(p-k).
9. Pokazać, że dla dowolnych liczb naturalnych a≤b≤c istnieje graf G taki, że K(G)=a, K'(G)=b, δ(G)=c.
K(G)- spójność wierzchołkowa, K'(G)- spójność krawędziowa, δ(G)-minimalny stopień wierzchołka. Istnieje taki graf G, że K(G)=1, K'(G)=1 i δ(G)=1 (dowolne drzewo!). I. Zakładamy, że K(G)=K'(G)=1 δ(G)=p, p≥1. RYS1.
10. Wykazać, że jeśli G- spójny, |E|≥1 to |E(G)| ≥ (χ(G) nad 2)
Graf G RYS można narysować tak, że graf jest pokolorowany na χ(G)=k kolorów. Więc 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 grafami 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) Mamy podzbiory dwuelementowe z kolorów. Bierzemy pokolorowanie o najmniejszej liczbie kolorów. Wybieramy ze zbioru pary zbiorów. Ponieważ jest pokolorowanie najmniejszą liczbą kolorów to pomiędzy tymi zbiorami musi być krawędź. Jeżeli by tej krawędzi nie było to cały zbiór można by pokolorować jednym kolorem. Zatem krawędzi jest co najmniej tyle co zbiorów.
11. χ(G)*χ(dopG)≥|V|=p
Malujemy G χ(G) kolorami. Dzielimy w ten sposób wierzchołki G na χ(G) podzbiory (w każdym wierzchołki tego samego koloru). W każdym podzbiorze są wierzchołki niezależne czyli w podzbiorze może być najwyżej β0 wierzchołków. Stąd χ(G)β0≥|V| (*). Niech S⊆V(G) będzie maksymalnym zbiorem niezależnych wierzchołków |S|=β0⇒ dopG zawiera podgraf Kβ0. Aby pokolorować Kβ0 potrzebne jest β0 kolorów. ⇒ β0≤χ(dopG) (**), (*) i (**) ⇒ χ(G)χ(dopG)≥|V|=p.
11a. Znaleźć wszystkie grafy G - spójne t, że G krytyczny i χ(G)=3
Jedynymi grafami 3-krytycznymi są nieparzyste cykle. Usunięcie dowolnej krawędzi spowoduje, że będziemy mogli pomalować te grafy dwoma kolorami - po usunięciu z cyklu krawędzi będzie to droga. Inne grafy niż nieparzyste cykle nie mogą być. D: Przypuśćmy, że graf H χ(H)=3 to zawsze znajdziemy taki podgraf H' który jest cyklem nieparzystym, więc usunięcie wszystkiego oprócz tego podgrafu nie zmniejszy liczby chrom. więc grafami 3-krytycznymi są cykle nieparzyste.
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. χ(G1+G2)=χ(G1)+χ(G2)
G1=(V1,E1) G2=(V2,E2) V1∩V2=pusty. G1+G2 jest grafem (V,E) gdzie V=V1∪V2, E=E1∪E2∪{(a,b) a∈V1, b∈V2}. RYS Graf G1 kolorujemy χ(G1) kolorami, graf G2 χ(G2) kolorami, ale innymi niż χ(G1). Otrzymuję pokolorowanie grafu G1 i G2 zatem χ(G1+G2)≤χ(G1)+χ(G2) (*). Zakładam, że χ(G1+G2)<χ(G1)+χ(G2) to znaczy, że wśród kolorów w G2 wystąpił przynajmniej jeden kolor, który był wzięty do G1. Istnieje wierzchołek w G2 u który jest pomalowany na taki sam kolor jak któryś z wierzchołków G1 - ten wierzchołek niech będzie v. Z def. grafu u i v są połączone krawędzią, mamy więc sprzeczność bo dwa wierzchołki sąsiadujące nie mogą być pomalowane na ten sam kolor. Stąd χ(G1+G2) ≥χ(G1)+χ(G2) (**). Z (*) i (**) mamy χ(G1+G2)=χ(G1)+χ(G2).
14. Udowodnij, że jeśli G jest grafem dwudzielnym 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 v0 v1…vmv0 będzie cyklem w grafie G i załóżmy, że v0∈A. Wtedy v1∈B, v2∈A itd. Ponieważ wierzchołek vm musi należeć do B, cykl ma długość parzystą.
“⇐” Jeśli każdy cykl w G jest parzystej długości to wtedy numerując te wierzchołki idąc z v1 do v2 możemy iść RYS. Wyróżniamy jeden wierzchołek 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 wierzchołki 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, vi, vi+1 sąsiadujące z v. Gdy mamy już te wierzchołki rozszerzamy cykl o v przez wyrzucenie krawędzi vivi+1 i dodanie krawędzi viv i vvi+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. K5=G+dopG więc |E(K5)|=|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|≥(n2 -3n+6)/2⇒ G ma cykl Hamiltona To zadanie jest w Rosie, jutro będę je miała!
Mamy pokazać, jaka jest minimalna ilość krawędzi w grafie, która gwarantuje, że graf ma cykl Hamiltona. Tw.Ore'a: Jeśli G ma n wierzchołków oraz deg(v)+deg(u)≥n dla każdej pary niesąsiednich wierzchołków to G ma cykl Hamiltona (deg(u) stopień wierzchołka u czyli ilość krawędzi z niego wychodzących). |V|=n. Maksymalna ilość krawędzi w grafie pełnym jest równa n!/2!(n-2)!=(n-1)n/2=(n2-n)/2. Z grafu pełnego usuwamy n-3 krawędzie wtedy (n2-n)/2 -(n-3)=(n2-3n+6)/2. Nie wprost. Po zaprzeczeniu warunku wyjściowego otrzymujemy |E|<(n2-3n+6)/2. Czyli mam sprawdzić co się dzieje gdy usunę n-2 krawędzi. Bierzemy dwa wierzchołki u i v, w grafie pełnym oba mają stopień n-1 i usuwamy krawędź je łączącą. Mamy więc dwa wierzchołki nie połączone krawędzią o stopniach n-2 RYS Jaka będzie suma stopni tych wierzchołków po usunięciu n-2 wierzchołków? n-2 +n-2-(n-3) =2n-4-n+3=n-1, a z twierdzenia Ore'a deg(u)+deg(v)≥n więc
sprzeczność czyli w takim grafie nie ma cyklu Hamiltona.
17A. Każdy graf K2s+1 ma 2-faktoryzację ma cykl Hamiltona
V={v1,....,v2s+1} zbiór wierzchołków. RYS1. Konstrukcja 2-faktora wybieramy ci=(vi,vi-1,vi+1,vi-2,vi+2,....,vi-s,vi+s,vi), ci są cyklami Hamiltona. RYS2. Liczba krawędzi/długość cyklu=liczba rozłącznych cykli Hamiltona, n=2s+1 n(n-1)/2n - liczba całkowita 2s+1-1/2=s.
18.Udowodnić, że jeśli graf G zawiera cykl Eulera G zawiera pewien cykl prosty.
Twierdzenie: Jeśli graf G zawiera cykl Eulera, to stopień każdego wierzchołka jest liczbą parzystą. Dowód: Przypuśćmy, że P jest cyklem Eulera w grafie G. Za każdym razem, gdy cykl P przechodzi przez wierzchołek, 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 wierzchołka musi być liczbą parzystą. Lemat: Jeśli w grafie G każdy wierzchołek jest stopnia co najmniej 2, to graf G zawiera cykl. Dowód: Załóżmy, że G jest grafem prostym. Niech v będzie dowolnym wierzchołkiem grafu G. Tworzymy trasę vv1v2… przez indukcję, wybierając jako v1 dowolny wierzchołek sąsiadujący z v, a następnie, ∀i>1 wybierając jako wierzchołek vi+1 dowolny wierzchołek sąsiadujący z vi, różny od vi-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 vk jest pierwszym takim wierzchołkiem, to część trasy znajdująca się między pierwszym i drugim wystąpieniem wierzchołka vk jest szukanym cyklem. Udowodniliśmy że jeśli G zawiera cykl Eulera, to stopień każdego wierzchołka jest liczbą parzystą, tzn. 2,4,6,…. Liczby te są ≥2 więc korzystając z lematu wykazaliśmy, że G zawiera cykl prosty.
19. G spójny ⇒G3 graf Hamiltona
Należy pokazać że każde dwie sąsiadujące w G wierzchołki są połączone drogą Hamiltona w G3 Wystarczy pokazać dla drzew bo każdy graf spójny zawiera drzewo rozpinające.(dowolny podgraf rozpinający czyli zawierający wszystkie wierzchołki grafu będący drzewem) Dowód indukcyjny względem wierzchołka. 1)dla p=1,2,3 - oczywiste. 2)załóżmy że warunek jest spełniony dla p-2
Teraz mamy drzewo o p wierzchołkach Gdy u i v są liśćmi to wyrzucamy u i v i mamy dwa drzewa RYS1 Jedno o 1 wierzchołku drugie o p-1 wierzchołkach RYS2.Gdyby nie był liściem RYS3.
19a. |E|≥2 ,K(G)≥2⇔((∀e,f∈E) e∩f≠∅ ⇔istnieje cykl prosty taki że e,f∈E(L) tzn. każde dwie krawędzie leżą na wspólnym cyklu prostym.
„⇒”jeśli graf jest dwuspójny to przez każde dwie krawędzie przechodzi cykl prosty. Bierzemy te dwie krawędzie o wspólnym wierzchołku a. Wtedy przez b i c przechodzi cykl prosty. a należy do części cyklu. Bierzemy tę część cyklu do której a nie należy dołączamy trójkąt i mamy cykl prosty przechodzący przez te dwie sąsiadujące krawędzie. „⇐”Graf nie ma liści. Zakładam że v rozpinający(czyli po wyjęciu wierzchołka i krawędzi z nim incydentnych rozspójniamy graf) leży na cyklu prostym , więc aby rozspójnić graf trzeba wyrzucić jeszcze jeden wierzchołek więc v nie jest rozspójniający.
20. Dwudzielny graf Hamiltona ma parzystą liczbę wierzchołków. To jest to samo zadanie co 71., tylko inaczej sformułowane.
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 v0 v1…vmv0 będzie cyklem w grafie G i załóżmy, że v0∈A. Wtedy v1∈B, v2∈A itd. Ponieważ wierzchołek vm musi należeć do B, cykl ma długość parzystą.
21.|V|≥5 (∀u,v∈V)(∃u-v droga Hamiltona) to K(G)≥3.
Wybieramy w grafie G dowolne u,v. Z zał. mamy u-v drogę Hamiltona. Wyrzucenie u i v nie rozspójni grafu G, gdyż dla każdego innego wierzchołka z G (różnego od wierzchołków u i v) jest to droga Hamiltona. która nie zawiera wierzchołków u i v. Ponieważ ∀u,v ∃droga Hamiltona. u-v więc wyrzucenie dowolnych dwóch wierzchołków nie rozspójni grafu G. ⇒ K(G)≥3.
22. G-spójny, 3-regularny hamiltonowski ⇒ χ'(G)=3
Graf jest spójny ⇔ ∀u,v∈V ∃u-v droga. Graf jest 3-reg. ⇔ z każdego wierzchołka wychodzą 3 krawędzie. Ponadto G jest grafem Hamiltona, czyli zawiera cykl Hamiltona., tzn cykl, który przechodzi przez wszystkie wierzchołki 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 Hami ltona. na przemian 2 kolorami (parzysta liczba wierzch. na pewno się uda). Teraz z każdego wierzchołka wychodzi jeszcze po jednej nie pokolorowanej dotychczas krawędzi. Na pewno nie będzie to krawędź łącząca 2 wierzchołki sąsiadujące ze sobą w cyklu Hamiltona.(już są pokolorowane). Malujemy te krawędzie trzecim kolorem - otrzymujemy χ'(G)=3. Rysunek - naokoło na okręgu wierzchołki będące w cyklu Hamiltona., a w środku - „trzecie” krawędzie.
23. δ(G)=d⇒G zawiera cykl prosty długości ≥d+1.
Bierzemy najdłuższą drogę w G. rys . Każdy z tych wierzchołków ma d sąsiadów leżących na tej drodze prostej(najdłuższej). Otrzymujemy odległość co najmniej d(ponieważ co najmniej d krawędzi wychodzi z v0 i spowrotem do niej wraca, czyli jest cykl.). Mamy więc odległość co najmniej d na drodze prostej i dodajemy np. krawędź v0-vd i otrzymujemy cykl prosty długości ≥d+1.
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?
Wybieramy przy pomocy algorytmu Kruskala najtańsze drzewo rozpinające T1. Zakładamy, że istnieje inne drzewo rozpinające T2 o tej samej wadze t, że T1≠T2 T1={e1...en}, wtedy ej∈T2 j∈{1...i-1} i ei∉T2. T2+ei ma dokładnie jeden cykl w którym istnieje krawędź e nie należąca do T1(bo jeśli należałyby wszystkie krawędzie to w T1 byłby cykl). e nie tworzy cyklu z e1...ei-1 i nie została wybrana przez algorytm Kruskala czyli ω(e)>ω(ei) skoro tak ω(T2-e+ei)<ω(T2) ponieważ T2-e+ei drzewo rozpinające to mamy sprzeczność z tym, że T1 najtańsze drzewo rozpinające.
25. T-drzewo,∀x,y∈V,x≠y,∃wT3x-y droga Hamiltona ⇒jest cykl Ham.
Dowód indukcja po wierzchołkach.n=1 OK., n=2 droga dł. 1 OK., n=3 graf pełny OK., n=4 graf pełny OK.,.... Usuwając z drzewa jedną z krawędzi łączących u-v otrzymujemy dwie składowe drzewa do jednej będzie należało u, a do drugiej v. W Zał. ind. jest, że dla każdych u,v składowych ∃ droga Hamiltona. rys Każde dwa różne wierzchołki są połączone drogą Hamiltona. rys wyrzucamy u0 krawędź i otrzymujemy dwie składowe. Istnieje wierzchołek sąsiadujący z y w (G3)T3. To jest T3 spójny Hamiltonowski.
26. T drzewo ⇔ ∀T1,T2 spójnych podgrafów T zachodzi T1∩T2≠∅⇒T1∩T2 jest spójnym podgrafem T.
„⇒” T drzewo⇒T spójny. Weźmy dowolne podgrafy spójne T1 i T2, rozłączne i dowolne wierzchołki u,v∈V(T1,T2). W T1 ∃u-v droga (ze spójności T1), w T2 ∃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 T1i T2 to te same czyli u-v droga jest zawarta w T1∩T2. Mamy więc u-v drogę w T1∩T2. Rozważone były dowolne wierzchołki u,v więc T1∩T2 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 T1 będzie v-s drogą zawartą w C zawierającą u i niech T2 będzie v-s drogą zawartą w T nie zawierająca u. rys Grafy T1 i T2 są spójne jako drogi i ich częścią wspólną T1∩T2 jest zbiór dwóch wierzchołków {v,s}-oczywiście jest to podgraf niespójny grafu T (sprzeczne z zał., że T1∩T2 jest podgrafem spójnym). Wniosek : w T nie może być cykli. Czyli T jako graf spójny, acykliczny jest drzewem.
27 ??????????????????????????
diamG⇒G ma drzewo rozpinające T takie, że diam T=2 (>2 ???)
przykładem takiego grafu jest cykl C długości 6. Drzewo rozpinające zawiera wszystkie wierzchołki i jest jego podgrafem. Nie jest cyklem więc jest drogą o dł. 4 diam p=4 czyli diam T>2.
Wniosek :Własność nie zawsze jest prawdą.
1. k-krytyczny ??? ≥2⇒G dwuspójny lub
2. G 3-krytyczny ⇒ G=C2n+1 dla pewnego n jasne, że χ(Kn)=n ⇒ można zbudować graf o dowolnej l. chromatycznej. Z drugiej strony χ(G)=1 ⇔ gdy G jest grafem pustym oraz χ(G)?????????????=2 ⇔ Gn - niepusty dwudzielny. Jeśli G jest dwudzielny to każdy cykl ma parzystą długość. Jeśli G niepusty to χ(G)=2 ⇔ G nie zawiera cyklu o nieparzystej długości. Zauważmy, że w szczególności każde drzewo z przynajmniej dwoma wierzchołkami jest α-chroamtyczne (podobnie jak dowolny graf cykliczny z parzystą liczbą wierzch.). to nie spełnia war k-kryt⇒K2. Przykład g. planarnego G którego δ(G)=5
28.T1,T2 - drzewa rozpinające G, e∈E(T1). Udowodnić, że w T2 istnieje krawędź f t,że T1-e+f jest drzewem rozpinającym G.
rys Mamy dwa drzewa rozpinające T1 i T2, e∈E(T1), T1-e jest drzewem którym do rozpinającego brakuje krawędzi dochodzącej do jednego wierzchołka (*), albo T1-e jest dwoma drzewami zawierającymi wszystkie wierzchołki (**). Jeśli e∈E(T2)⇒jest dobrze, wystarczy przyjąć f=e.(*)T2 ma pewną krawędź (co najmniej jedną dochodzącą do wierzchołka, którego T1-e (bo T2 rozpinający) nie obejmuje. Biorę dowolną krawędź z T2 która połączona jest z tym wierzchołkiem, dołączamy ją do T1-e. W ten sposób otrzymujemy drzewo rozpinające. Jest to drzewo, ponieważ T1-e nie miało żadnej krawędzi łączącej z wierzchołkiem (*) czyli dodanie krawędzi nie utworzy nam cyklu. Po wyrzuceniu e otrzymamy dwa drzewa (które nie są połączone żadną krawędzią) T1', T2''. T1 zawiera wszystkie wierzchołki wystarczy dodać jedną krawędź łączącą T1',T2'' aby otrzymać drzewo rozpinające. T2 jest drzewem rozpinającym. e≠T2 musi istnieć jakaś krawędź między nimi T1',T2''. Bierzemy którąś z tych krawędzi (**) dodajemy do T1-e. Otrzymujemy drzewo rozpinające między T1' i T1'' nie było żadnych krawędzi więc nie będzie cyklu.
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 wierzchołki cyklu, ale nie wszystkie krawędzie. Jeśli z naszego grafu wyrzucimy jedną krawędź, to powstanie nam droga prosta P5. Wiemy, że diamPn=n-1 (diamPn - średnica drogi prostej o n wierzchołkach), więc diamP5=4. Zatem nasza własność nie zachodzi, bo miało wyjść diam=2.
30. a)α0(G)≥β1(G), b) α1(G)≥β0(G)
a)Weźmy najmniejszy zbiór niezależnych krawędzi S w grafie G. Warunkiem koniecznym istnienia pokrycia T wierzchołkami G jest aby ∀e∈S ∃v∈T. Ponieważ krawędzie S są niezależne musimy wybrać z każdej krawędź co najmniej jeden wierzchołek, a więc liczność każdego pokrycia wierzchołków jest większa od liczności S ⇒ α0(G)≥β1(G). b)Ponieważ ∀G α0(G)+β0(G)=α1(G)+β1(G)=p to z tegi i punktu a) wynika p-β0(G)≥p-α1(G)⇔α1(G)≥β0(G)
31. α0(G)+β0(G)=|V|=n
Niech N - pokrywa E (każda krawędź ma co najmniej jeden koniec w N), |N|=α0. V\N - jest niezależnym zbiorem wierzchołków. β0≥|V\N|=n-α0 ⇒α0+β0≥n(*). Niech M=β0 i M niezależny. V\M - zbiór pokrywający E. Więc |V\M|≥α0 czyli n-β0≥α0 ⇒ n≥α0+β0(**). Z (*) i (**) wynika, że α0(G)+β0(G)=n.
32. Scharakteryzować te grafy dla których α1=β1.
|V|=p. α1+β1=p⇒α1=p/2 i β1=p/2 czyli graf ma postać rys liniowa niezależność krawędzi tzn. α1=β1 istnieje faktor w grafie. Dla G- planarny K3⊆G⇒ξ'(G) ≤4.
33. ∀G α0≥δ(G)
δ(G)=min deg v. Bierzemy |M|=α0 - najmniejsza liczba wierzchołków pokrywająca wszystkie krawędzie. M⊆V. Zakładamy, że :∃ v0∉M⇒M≥N(v0) ⇒|M|≥degv0≥δ, gdzie N(v0) - to ilość krawędzi wychodzących z v0. Wszystkie wierzchołki nie mogą należeć do M, musi istnieć co najmniej jeden wierzchołek nie należący do M. Gdyby taki nie istniał to krawędzie byłyby pokryte dwa razy. Zatem otrzymujemy α0≥δ.
34. ∀G α0(G) ≥β1(G) (tw. Mengera w jedną stronę)
∀u,v∈V(G) α0(G)-minimalna liczba wierzchołków, które rozdzielają u od v, β1(G) maksymalna liczba rozłącznych krawędzi z u do v. Jeżeli zbiór wierzchołków rozdziela u od v, to musi on zawierać co najmniej jeden wierzchołek każdej z β1 rozłącznych krawędzi, a więc α0≥β1.
35.α1=β1 , |V|=p
ROZW.: Tw. Gallai: Dla każdego nie trywialnego G o p- wierzchołkach i δ(G)>0 α0(G)+β0(G)=α1(G)+β1(G)=p Z tw. Gallai α1+β1=p β1=p/2 α1=p/2 α1=β1 G ma 1 faktor , istnieje podgraf rozpinający 1-regularny G ma jeden faktor β1=p/2 2β1=p α1β1 p=α1+β12β1=p α1+β1=2β1
α1=2β1-β1 α1=β1.
36.G- dwudzielny ⇒ |E|≤α0β0
α0 - najmniejsza liczność zbioru wierzchołków pokrywająca wszystkie krawędzie, β0 - największa liczność niezależnego zbioru wierzchołków. Równość zachodzi tylko dla grafu pełnego dwudzielnego. |E|≤ α0 Δ≤ α0β0 bo wiem, że β0δ≤|E|≤α0Δ i w grafie dwudzielnym Δ≤ β0. Zatem |E|≤α0β0
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.
38.K(Gn)≥n |V|≥n+1 G-spójny
ROZW.: (nie wprost) K(Gn)≤n-1 ,czyli ∃s∈V |s|=n-1. Gn-s - niespojny, czyli nie ma w nim x-y drogi; p - najkrótsza x-y droga w G. x=x0 y1=x2 ...xk ⇒ p jest też w Gn. Aby popsuć p w G2 należy usunąć dwa wierzchołki. Rys. 8.1. w G3 - wyrzucamy 3 wierzchołki w G4 - wyrzucamy 4 wierzchołki. Żeby popsuć w Gn należy usunąć n wierzchołków. Usunęliśmy tylko n-1 wierzchołków. Aby popsuć drogę p w Gn trzeba z każdej x-y drogi wyrzucić co najmniej n wierzchołków. a) n=2 K(G2)≥2 - prawdziwe b) K(Gn-1)≥n-1 czyli w Gn-1 istnieje n-1 rozłącznych dróg prostych dla Gn. zał. K(Gn)<n ∃ |u|=n-1
39.G spójny ⇔ ∀ podziału V=V1+V2; V1,V2≠∅, V1∩V2=∅ istnieje w G krawędź uv taka, że u∈V1 a v∈V2
„⇒” Zakładamy, że G spójny. Zatem oba podziały muszą być połączone więc istnieje krawędź łącząca wierzchołek v z V1 z wierzchołkiem u z V2. „⇐” Przypuśćmy, że G jest niespójny ⇒ G ma co najmniej 2 składowe. Niech jedną składową będzie V1 a pozostałe składowe to V2. 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 mają wspólny wierzchołek.
Zakładam, że nie mają wspólnego wierzchołka. Mamy dwie najdłuższe drogi: P1 i P2. Rys. Wybieram na drodze P1 wierzchołek v1, a na drodze P2 wierzchołek u1. Ponieważ graf ten jest spójny, to istnieje droga P: v1-u1. Wierzchołek wspólny drogi P1 i P oznaczamy v, a wierzchołek wspólny drogi P i P2 oznaczamy wierzchołkiem u tzn. że pomiędzy wierzchołkiem u i v nie ma żadnego wierzchołka należącego do P1 lub do P2. Ponieważ długość drogi między v, u jest >=1, więc istnieje droga v0-u0 (gdzie v0 końcowy wierzchołek drogi P1, a u0 drogi P2). Droga v0-u0 jest dłuższa od drogi P1 i P2 o co najmniej 1. Otrzymujemy sprzeczność bo drogi P1 i P2 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=[n2- 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.
42.K(G') = K(G) - 1 , gdzie G- spójny
G' - podgraf G otrzymamy przez wyrzucenie jednego wierzchołka. n- liczba wierzchołków grafu G; To jest to samo zadanie co 37 tylko inaczej sformułowane!
43.|V|≥3 G- spójny ⇒K(G2) ≥ 2
Bierzemy dowolne wierzchołki u i v. Są one spójne więc jest między nimi droga a na niej wierzchołki Rys. 1.1 G2 mamy dodatkowo Czyli u iv leżą na wspólnym cyklu więc K(G)≥2
44.G spójny, to |V(G)| ≥K(G)(diam(G)-1)+2
Weźmy u i v (u,v∈G) takie, że dist(u,v)=diam(G). K(G)-spójność wierzchołkowa. S- zbiór oddzielających u-v. |S|≥K(G) bo K(G) jest wartością najmniejszego zbioru oddzielającego u-v. RYS Na u-v leży diam(G)-1 wierzchołków G, bo dist(u,v)=diam(G). Z tw. Mengera mamy, że w G istnieje K(G) rozłącznych u-v dróg. Zatem V(G) ≥K(G)(diam(G)-1)+2, gdzie dodane 2 to wierzchołki u i v więc |V(G)| ≥K(G)(diam(G)-1)+2.
45.G spójny, |V|≥3 wówczas G2 dwuspójny.
Weźmy w G2 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: P1 uv1v3v i P2 uv2v. Dla drogi u-v o nieparzystej długości [rys2]mamy: P1 uv1v3v i P2 uv2v4v. Ogólnie mamy P1 uv1v3...v2k-1v, P2 uv2v4...v2kv. Ponieważ dla każdych dwóch nie sąsiednich wierzchołków u i v istnieją w G2 dwie wewnętrznie rozłączne drogi czyli K(G2) ≥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 C1 taki, że x,z∈C1 i istnieje cykl C2 taki, że y,z∈C2. Aby dojść z y do x przechodząc przez z należy wyjść z y i iść cyklem C2 aż do przecięcia się obu cykli, wtedy przechodzimy na cykl C1 i idziemy do z a następnie do x. Jeżeli na cyklu C1 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
ROZW.: Bierzemy wszystkie rozłączne u-v drogi, żeby zbiór był u-v rozdzielający musi mieć cc najmniej jeden wierzchołek z każdej z tych dróg . Najkrótsza droga ma dist(u,v) - 1 wierzchołków nie licząc u i v. Zbiory u-v oddzielające konstruuje się w następujący sposób : wierzchołki każdej z rozłącznych u-v dróg indeksujemy kolejnymi liczbami naturalnymi. Tworząc zbiory u-v oddzielające z każdej drogi rozłącznej u-v drogi biorę wierzchołki o tym samym indeksie. W ten sposób dostanę dist(u,v)-1 zbirów rozłącznych, nie może być ich mniej, bo szukamy maksymalnej liczby takich zbirów. (bo dist(u,v)-1 jest najkrótszą drogą).
48.k(G)≥2 G - zawiera drogę prostą długości l ≥1 wówczas G zawiera cykl prosty długości większej √2 l
ROZW.: W - u ,v droga długości l , G dwuspójny. Istnieją dwie rozłączne u-v drogi w G i W1, W2
|W1∩W|=V1 ≥ 2 |W2∩W|=V2 ≥ 2 V1+V2=2 ≤ długość cyklu |w1∪w2|≤C(G) ,gdzie C(G)- długość najdłuższego cyklu. Wierzchołki ze zbioru W1∩W dzielą drogę W na |V1|-1 kawałków, najdłuższy ma więc l≠|V1|- 1 Rys.13.1 Przypuśćmy że l jest najdłuższym kawałkiem. Mamy więc cykl a) l≠W1-1 C(G)>l/V1-1 2l/C(G) <V1+V2-2 ≤C(G) 2l/C(G) < C(G) ⇒C(G) > √2ּ l 2l < C2(G) √2l < C(G).
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ń k. Jeśli jakiś wierzchołek miałby stopień mniejszy od k, to usuwając wszystkie wierzchołki sąsiadujące z nim rozspójnimy 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∈Vdegv≥ nk stąd |E|≥nk/2.
50.G ≅ dopG, |V|>1 ⇒ diamG=2 lub diamG=3
Bierzemy wierzchołek o stopniu i, musi istnieć drugi wierzchołek o stopniu n-1-i.Bierzemy dwa dowolne wierzchołki u i v. Dla wierzchołka u szukamy wierzchołka dowolnego o stopniu u-1-i. Droga między u i v jest co najmniej 2. RYS1(z tw. Dirichleta) Zakładam, że w grafie istnieje droga między a i b Jej długość wynosi 4, bo G ≅ dopG więc w dopG musi istnieć także najkrótsza droga dł. 4. Załóżmy, że jest to droga między a' i b'. Drogą eliminacji można pokazać, nie jest to możliwe. Otrzymamy sprzeczność z założeniem, że droga między a i b wynosi 4. diam(G)*maxx,y∈V distG (x,y). Zakładam że najkrótsza droga z u do v =4.RYS2
1)bierzemy z u-v drogi dwa wierzchołki to w dopG RYS3. W diam 2 gdy w G nie sąsiadują, diam 1 gdy w G sąsiadują.
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. Warunki konieczne to: 1. n≤p-1 (stopień nie może przekraczać liczby wierzchołków ). 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 Kp 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.Dla każdego G |V| = 6 ⇒ G lub dopG zawiera K3 Znaleźć max. liczbę k taką że dla każdego grafu G o k- wierzchołkach G lub dopG zawiera K3
Dla K5 nie jest spełnione rys1.
Rozważam graf K6 z każdego wierzchołka wychodzi 5 krawędzi. Graf G koloruje na zielono a dopełnienie grafu G na czerwono. Biorę dowolny wierzchołek v i zakładam że wychodzą z niego co najmniej 3 krawędzie zielone rys2. Np. e1, e2, e3 są zielone jeżeli z wierzchołka v3 weźmiemy krawędź zieloną to otrzymamy K3 zielony czyli G zawiera K3. rys3. e6 krawędź zielona. Jeżeli żadna z wychodzących krawędzi z wierzchołka v3 nie jest zielona to otrzymamy czerwone K3 czyli dopełnienie G jest (zawiera) K3. Rys4. Krawędzie e3, e6, e7, e8, e9 wychodzące z v1 są czerwone. Rys 5.
53.Jaka jest najmniejsza ilość krawędzi w grafie o n- wierzchołkach.
Załóżmy, że n ≥ 2, liczba krawędzi w grafie pełnym |E| = (n-1)*n/2. Aby rozspójnić graf wystarczy usunąć n-1 krawędzi których jednym końcem jest ten sam wierzchołek v ∈V wtedy graf ma postać: rys.1 a ilość krawędzi w tym grafie jest równa |E| = (n-1)*n/2 - (n-1) = (n-1)(n-2)/2. Jest to największa ilość krawędzi w tym grafie o n- wierzchołkach. Zakładam że tak nie jest czyli nie istnieje zbiór S krawędzi grafu pełnego, że |S| < (n-1) i graf G-S jest niespójny czyli w G-S mamy dwie składowe V1 i V2. rys2 1) V(G) = 2=n wtedy G: rys3. |S| = 1 = (2-1) = n-1 2) V(G) = 3 = n wtedy sprzeczność z założeniem. Aby rozspójnić ten graf potrzebne są dwie krawędzie |S| = 2 = (2-1) = n-1 sprzeczność. |S| = (n-1)(n-2)/2 |S| = n*(n-1)/2 - (n-1) k*(n-1)/2 + (n-k)(n-k-2)/2 znak + to funkcja rys.4 1≤k ≤ n-1 1 dla k=1 k = n-1. Na końcach przedziału wstaw pewny maksym. o dwóch składowych grafu pełnego.
54. K(G) ≤λ(G) ≤δ(G)
λ(G) ≤δ(G) oczywiste, bo biorąc wierzchołek o najmniejszym stopniu, wyrzucając wszystkie krawędzie wychodzące z niego rozspójniamy graf. Wyrzuciliśmy co najwyżej tyle krawędzi ile wychodziło z tego wierzchołka, czyli min deg(v). K(G) ≤λ(G) - spójność krawędziowa, K(G) - spójność wierzchołkowa. dowód przez indukcję względem λ(G). 1. λ(G)=1 może być tak: RYS1. po usunięciu tych krawędzi otrzymamy grafy niespójne. 2. Zakładam, że dla λ(G)=k-1 jest prawdziwe K(G)<=λ(G). 3. Pozostało rozpatrzyć dla λ(G)=k. Mamy wtedy graf RYS2. Usuwamy z tego grafy dowolną jedną krawędź rozpinającą. Otrzymamy graf λ(G)=k-1. Z zał. ind. istnieje co najwyżej k-1 wierzchołków mamy graf niespójny. Dokładamy do niego tę usuniętą krawędź i wtedy otrzymamy graf dalej niespójny (bo usuwając k-1 krawędzi mogliśmy usunąć wierzchołki tych krawędzi wtedy k-1<k albo graf ten będzie spójny i usuwam wtedy wierzchołek i mamy graf niespójny).?????????????
55. Każdy graf K2,S ma 1-faktoryzację dla s≥1 (ile drzew spinających ma graf K2,S?)
RYS. Każde drzewo spinające grafu K2,S zawiera jedną z dwóch krawędzi uvi lub viw dla każdego i oraz jedną dodatkową krawędź. Liczba drzew spinających jest więc równa 2S*S/2=S*2S-1.
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 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ównoznaczne ze znalezieniem cyklu Hamiltona.
Dla n- nieparzystego Każdy cykl wykonany konikiem jest parzystej długości, czyli nie ma cyklu przechodzącego przez wszystkie wierzchołki.
Dla n- parzystego i n=2 nie możliwe są żadne ruchy, ale już dla n>2 i n- parzystego da się.
57. V={a1,...,ak} a ∈{0,1}} w1,v1∈E jeśli różnią się na dokładnie jednym miejscu udowodnić, że Qk jest regularny oraz znaleźć liczbę krawędzi, wierzchołków.
Qk=<V,E>; V={a1,...,ak} a ∈{0,1}} Takich ciągów istnieje 2k. Jeśli v1,v2∈E to muszą różnić się na dokładnie jednym miejscu. V vi=a1,..ak vj=b1,...bk istnieje n takie, że an≠bn to każdy wierzchołek vi jest indukowany k krawędziami to G- k-regularny. Ilość wierzchołków w tym zbiorze wynosi 2k, zatem ilość krawędzi w tym zbiorze wynosi (k*2k)/2
59. dopG=G (⇔G jest izomorficzny ze swoim dopełnieniem)⇒|v|=4k, lub |v|=4k+1
Aby graf G był izomorficzny ze swoim dopełnieniem, to oba grafy muszą mieć tę samą ilość wierzchołków 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)/2 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 G1 i G2 rozdzielne, czyli takie, że żaden wierzchołek należący do G1 nie sąsiaduje z żadnym wierzchołkiem należącym do G2. Jeżeli teraz weźmiemy dopG to wszystkie wierzchołki z klasy G1 sąsiadują ze wszystkimi wierzchołkami z klasy G2. Teraz a) dla dowolnych u∈G1 i v∈G2 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ę.
61. Ile jest liści w drzewie T, które ma n wierzchołków stopnia i
i=1,2...m= max deg v
Drzewo jest to graf spójny acykliczny o |V|=|E|+1 wierzchołków; ni wierzchołków stopnia i dla i=1..
deg v=2|E|=1*n1+2*n2+...+m*nm zatem 1*n1+2*n2+...+m.*nm=2|v|-2, ale n1+n2+...+nm= |V|-przy założeniu, że nie ma graf wierzchołków izolowanych, czyli stopnia 0. Skoro drzewo to graf spójny to wierzchołków stopnia 0 nasz graf nie posiada. 1*n1+2*n2+...+m.*nm=2(n1+n2+...+nm)-2 czyli
2-n1+n3+3n5+5n7+...+(m-2)nm=0 2-n1=-[+3n5+5n7+...+(m-2)nm] 2-n1=-(i-2)ni 2+(i-2)ni=n1
m=2 to (i-2)ni=0 m=3 to nn m=4 to n1=2+n3+2n4 liści w drzewie jest conajmniej 2
62 (z 66). G dwuspójny, to każde dwie sąsiednie krawędzie leżą na pewnym cyklu prostym.
Indukcja względem n
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 a1, …, an będą dowolnymi dodatnimi liczbami całkowitymi. Rozważmy n szufladek. Umieśćmy w szufladkach n podzbiorów {a1}, {a1,a2}, …, {a1,a2,…,an} 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=(V1,E,V2) będzie grafem dwudzielnym (w którym zbiór wierzchołków jest podzielony na V1 i V2, a każda krawędź łączy element należący do V1 z elementem należącym do V2). Rozważmy w grafie G cykl v1,v2,v3,…,vn-1,vn,v1. Załóżmy np. że v1∈V1 itd. Wówczas istnienie krawędzi v1v2 zapewnia, że v2∈V2: podobnie v3∈V1 itd. Tak więc mamy v1∈V1, v2∈V2, v3∈V1,…, vn-1∈V1, vn∈V2, v1∈V1 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 v0 v1…vmv0 będzie cyklem w grafie G i załóżmy, że v0∈A. Wtedy v1∈B, v2∈A itd. Ponieważ wierzchołek vm 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ę vv1v2… przez indukcję, wybierając jako v1 dowolny wierzchołek sąsiadujący z v, a następnie, ∀i>1 wybierając jako wierzchołek vi+1 dowolny wierzchołek sąsiadujący z vi, różny od vi-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 vk jest pierwszym takim wierzchołkiem, to część trasy znajdująca się między pierwszym i drugim wystąpieniem wierzchołka vk jest szukanym cyklem.
73.Graf Kn ma nn-2 drzew spinających.
Każdemu drzewu oznakowanemu mającemu n wierzchołków odpowiada dokładnie jedno drzewo spinające grafu Kn. Odwrotnie, z każdego drzewa spinającego grafu Kn 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 CnH2n+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 grafu pełnego Kn wynosi: χ'(Kn)=n-1 dla n parzystych i χ'(Kn)=n dla n nieparzystych.
Każdy wierzchołek grafu Kn 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 χ'(Kn)=n, opisując sposób kolorowania krawędzi grafu Kn 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 Kn 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 Kn-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 Kn za pomocą n-1 kolorów: przypadek n=8 pokazano na rysunku.
80.Niech (V1,V2,E) będzie grafem dwudzielnym o największym 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 V1). Składowa ta jest drogą o początku w v∈V1 i krawędziach pokolorowanych kolejno kolorami c', c, c',…. Droga ta nie może kończyć się w wierzchołku w∈V2; 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 e1=vv1,…,er=vvr. Niech G' będzie grafem (V,E\{e1,…,er}). 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 v1,…,vr 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 ei. W szczególności jest jeden taki kolor dla krawędzi e1 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.
Legenda: Zadania na czarno poprawie jutro, na zielono nikt nie jarzy więc prawdopodobnie takich nie będzie! Siwe są dobre!