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. Załóżmy, że istnieje wierzch. stopnia mniejszego od 5, np. 4. Wyciągnięcie 4 sąsiadujących wierzch. 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.(regiony są zamknięte wtedy gdy w grafie jest cykl, minimalnym ograniczeniem regionu będzie obwód grafu czyli najkrótszy cykl w grafie).
Tw. Eulera Niech G będzie rysunkiem płaskim spójnego grafu płaskiego gdzie f oznacza liczbę regionów
wtedy |V| - |E| + 2=f . W ten sposób 2|E|≥r (|E|-|V|+2)(bo każda krawędź należy do co najmniej dwóch regionów.)
3. Nie istnieje graf planarny o 5 regionach t,ż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 wierzch. 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. (Tu tw. z którego skorzyst. trzeba jeszcze udowodnić. Zad na połowę pktów.). Czyli sprzeczność. RYS
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 wierzch. 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 wierzch. 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.
9. Pokazać, że dla dowolnych liczb naturalnych a≤b≤c istnieje graf G t,że K(G)=a, K'(G)=b, δ(G)=c.
K(G)- spójność wierzchołkowa, K'(G)- spójność krawędziowa, δ(G)-minimalny stopień wierzch.. 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.
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 wierzch. p1,…,pn. |p1|+|p2|+…+|pn|. Co najmniej jeden z tych podzbiorów ma liczność |pi|≥p/n. Wszystkich wierzch 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+…+cχ(G)≤χ(G)(p-k), a więc χ(G)≥p/(p-k).
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 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 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 wierzch. 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 wierzch. 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 wierzch. 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. wierzch. 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 wierzch. 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.
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 wierzch.ch 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 wierzch.ch. 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 wierzch. G na χ(G) podzbiory (w każdym wierzch. tego samego koloru). W każdym podzbiorze są wierzch. niezależne czyli w podzbiorze może być najwyżej β0 wierzch.. Stąd χ(G)β0≥|V| (*). Niech S⊆V(G) będzie maksymalnym zbiorem niezależnych wierzch. |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 wierzch., 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 wierzch. 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 wierzch. w G2 u który jest pomalowany na taki sam kolor jak któryś z wierzch. G1 - 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 χ(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 wierzch. na dwa zbiory rozłączne A i B w taki sposób, by każda krawędź grafu G łączyła wierzch. ze zbioru A z wierzch. 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ż wierzch. 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 wierzch. idąc z v1 do v2 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 Ham.
Weźmy G-v, ma on cykl Ham. i n-1 wierzch.. RYS1. Ponieważ degv>(n-1)/2 więc istnieją dwa wierzch. sąsiadujące ze sobą na tym cyklu, vi, vi+1 sąsiadujące z v. Gdy mamy już te wierzch. 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 Ham.. RYS2
16.Znajdz najmniejsze n t,że dla każdego grafu o n wierzch.ch |V|=n G ma cykl lub dopG ma cykl.
1,2 - oczywiste, 3-RYS1, 4-RYS2, 5: graf pełny o 5 wierzch.ch ma 10 krawędzi. Załóżmy, że G i dopG nie mają cyklu. W grafie o n wierzch.ch maksymalna ilość krawędzi jaką należy poprowadzić aby nie było żadnego cyklu to n-1.(Tw. Graf o n wierzch.ch 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 Ham. 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 Ham.. Tw.Ore'a: Jeśli G ma n wierzch. oraz deg(v)+deg(u)≥n dla każdej pary niesąsiednich wierzch. to G ma cykl Ham. (deg(u) stopień wierzch. 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 wierzch. u i v, w grafie pełnym oba mają stopień n-1 i usuwamy krawędź je łączącą. Mamy więc dwa wierzch. nie połączone krawędzią o stopniach n-2 RYS Jaka będzie suma stopni tych wierzch. po usunięciu n-2 wierzch.? 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 Ham..
17A. Każdy graf K2s+1 ma 2-faktoryzację ma cykl Ham.
V={v1,....,v2s+1} zbiór wierzch.. RYS1. Konstrukcja 2-faktora wybieramy ci=(vi,vi-1,vi+1,vi-2,vi+2,....,vi-s,vi+s,vi), ci są cyklami Ham.. RYS2. Liczba krawędzi/długość cyklu=liczba rozłącznych cykli Ham., 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 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ę vv1v2… przez indukcję, wybierając jako v1 dowolny wierzch. sąsiadujący z v, a następnie, ∀i>1 wybierając jako wierzch. vi+1 dowolny wierzch. sąsiadujący z vi, różny od vi-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 vk jest pierwszym takim wierzch., to część trasy znajdująca się między pierwszym i drugim wystąpieniem wierzch. vk 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.
19. G spójny ⇒G3 graf Ham.
Należy pokazać że każde dwie sąsiadujące w G wierzch. są połączone drogą Ham. w G3 Wystarczy pokazać dla drzew bo każdy graf spójny zawiera drzewo rozpinające.(dowolny podgraf rozpinający czyli zawierający wszystkie wierzch. grafu będący drzewem) Dowód indukcyjny względem wierzch.. 1)dla p=1,2,3 - oczywiste. 2)załóżmy że warunek jest spełniony dla p-2
Teraz mamy drzewo o p wierzch.ch Gdy u i v są liśćmi to wyrzucamy u i v i mamy dwa drzewa RYS1 Jedno o 1 wierzch. drugie o p-1 wierzch.ch 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) ]
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 l1 i l2 RYS2. „⇐”Skoro każde dwie sąsiednie krawędzie leżą na cyklu prostym więc graf nie ma liści czyli wierzch stopnia 1. Zakładam że nie zachodzi K(G)≥2.Czyli G nie jest dwuspójny i v leżący na cyklu prostym rozpinający(czyli po wyjęciu wierzch i krawędzi z nim incydentnych rozspójniamy graf) . Sprzeczność bo skoro v leży na cyklu prostym to aby rozspójnić graf trzeba wyjąć jeszcze co najmniej jeden wierzch czyli K(G)≥2.
20. Dwudzielny graf Ham. ma parzystą liczbę wierzch.. To jest to samo zadanie co 71., tylko inaczej sformułowane.
Ponieważ G jest dwudzielny, więc możemy podzielić jego zbiór wierzch. na dwa zbiory rozłączne A i B w taki sposób, by każda krawędź grafu G łączyła wierzch. ze zbioru A z wierzch. 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ż wierzch. vm musi należeć do B, cykl ma długość parzystą.
21.|V|≥5 (∀u,v∈V)(∃u-v droga Ham.) to K(G)≥3.
Wybieramy w grafie G dowolne u,v. Z zał. mamy u-v drogę Ham.. Wyrzucenie u i v nie rozspójni grafu G, gdyż dla każdego innego wierzch. z G (różnego od wierzch. u i v) jest to droga Ham.. która nie zawiera wierzch. u i v. Ponieważ ∀u,v ∃droga Ham.. u-v więc wyrzucenie dowolnych dwóch wierzch. nie rozspójni grafu G. ⇒ K(G)≥3.
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.
23. δ(G)=d⇒G zawiera cykl prosty długości ≥d+1.
Bierzemy najdłuższą drogę w G. rys . Każdy z tych wierzch. 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, ∃wT3 x-y droga Ham. ⇒ jest cykl Ham.
Dowód indukcja po wierzch.ch.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 Ham.. rys Każde dwa różne wierzch. są połączone drogą Ham.. rys wyrzucamy u0 krawędź i otrzymujemy dwie składowe. Istnieje wierzch. sąsiadujący z y w (G3)T3. To jest T3 spójny Ham..
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 wierzch. 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 wierzch. 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 wierzch. 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 wierzch. {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 t,że diam T=2 (>2 ???)
przykładem takiego grafu jest cykl C długości 6. Drzewo rozpinające zawiera wszystkie wierzch. 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 wierzch.mi 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
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.
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 wierzch. (*), albo T1-e jest dwoma drzewami zawierającymi wszystkie wierzch. (**). Jeśli e∈E(T2)⇒jest dobrze, wystarczy przyjąć f=e.(*)T2 ma pewną krawędź (co najmniej jedną dochodzącą do wierzch., którego T1-e (bo T2 rozpinający) nie obejmuje. Biorę dowolną krawędź z T2 która połączona jest z tym wierzch., 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 wierzch. (*) 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 wierzch. 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 wierzch. 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 wierzch.ch), 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 wierzch.mi G jest aby ∀e∈S ∃v∈T. Ponieważ krawędzie S są niezależne musimy wybrać z każdej krawędź co najmniej jeden wierzch., a więc liczność każdego pokrycia wierzch. 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 wierzch.. β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.
33. ∀G α0≥δ(G)
δ(G)=min deg v. Bierzemy |M|=α0 - najmniejsza liczba wierzch. 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 wierzch. nie mogą należeć do M, musi istnieć co najmniej jeden wierzch. 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 wierzch., które rozdzielają u od v, β1(G) maksymalna liczba rozłącznych krawędzi z u do v. Jeżeli zbiór wierzch. rozdziela u od v, to musi on zawierać co najmniej jeden wierzch. każdej z β1 rozłącznych krawędzi, a więc α0≥β1.
35.α1=β1, |V|=p
Tw. Gallai: Dla każdego nie trywialnego G o p- wierzch.ch 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 wierzch. pokrywająca wszystkie krawędzie, β0 - największa liczność niezależnego zbioru wierzch.. 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 wierzch. albo nie zmienia K(G) albo zmniejsza go o jeden. (Z def. spójności - istnieje zbiór S t,że wyjmując którykolwiek wierzch. 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
(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 wierzch.. Rys. 8.1. w G3 - wyrzucamy 3 wierzch. w G4 - wyrzucamy 4 wierzch.. Żeby popsuć w Gn należy usunąć n wierzch.. Usunęliśmy tylko n-1 wierzch.. Aby popsuć drogę p w Gn trzeba z każdej x-y drogi wyrzucić co najmniej n wierzch.. 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 t,ż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 wierzch. v z V1 z wierzch. 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 wierzch.
Zakładam, że nie mają wspólnego wierzch.. Mamy dwie najdłuższe drogi: P1 i P2. Rys. Wybieram na drodze P1 wierzch. v1, a na drodze P2 wierzch. u1. Ponieważ graf ten jest spójny, to istnieje droga P: v1-u1. Wierzch. wspólny drogi P1 i P oznaczamy v, a wierzch. wspólny drogi P i P2 oznaczamy wierzch. u tzn. że pomiędzy wierzch. u i v nie ma żadnego wierzch. 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 wierzch. 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 wierzch..
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 wierzch.. 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 wierzch. 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 wierzch.. n- liczba wierzch. grafu G; To jest to samo zadanie co 37 tylko inaczej sformułowane!
43.|V|≥3 G- spójny ⇒K(G2) ≥ 2
Patrz zad. 45.
44.G spójny, to |V(G)| ≥K(G)(diam(G)-1)+2
Weźmy u i v (u,v∈G) t,ż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 wierzch. 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 wierzch. 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 wierzch. 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 wierzch. 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 wierzch.≥2 to G zawiera pewien cykl prosty. Mamy dwa wierzch., które tworzą cykl. Każde dwa wierzch. leżą na cyklu prostym. Istnieje cykl C1 t,że x,z∈C1 i istnieje cykl C2 t,ż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 wierzch. 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 wierzch. 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 wierzch. z każdej z tych dróg . Najkrótsza droga ma dist(u,v) - 1 wierzch. nie licząc u i v. Zbiory u-v oddzielające konstruuje się w następujący sposób : wierzch. 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ę wierzch. 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. Wierzch. 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 wierzch. grafu ma stopień k. Jeśli jakiś wierzch. miałby stopień mniejszy od k, to usuwając wszystkie wierzch. sąsiadujące z nim rozspójnimy graf i to byłoby sprzeczne K(G)=k. Z każdego wierzch. 1..n wychodzi co najmniej k- krawędzi. Dodając stopnie wierzch. 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 wierzch. o stopniu i, musi istnieć drugi wierzch. o stopniu n-1-i.Bierzemy dwa dowolne wierzch. u i v. Dla wierzch. u szukamy wierzch. 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 wierzch. 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- wierzch.
Jeśli n i p nieparzyste to odpada. Warunki konieczne to: 1. n≤p-1 (stopień nie może przekraczać liczby wierzch. ). 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 wierzch. to n=2.W dowolnym cyklu dł. nieparzystej łączymy co drugi wierzch., wtedy otrzymamy graf 4-regularny. Następnie w tym samym grafie łączymy co trzeci wierzch., 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 wierzch. wychodzi p-1 krawędzi, czyli dla p- nieparzystego (p-1) parzyste. p - parzyste ⇒stopień wierzch. 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 wierzch. naprzeciwko siebie i łącząc wierzch. cyklu parzystego otrzymamy graf 3-regularny. 5-regularny otrzymamy z 4-regularnego przez połączenie wierzch. leżących naprzeciwko siebie. 7-regularny otrzymamy z 6-regularnego przez połączenie wierzch. 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 K3 Znaleźć min liczbę k taką że dla każdego grafu G o k-wierzch. G lub dog zawiera K3 (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.
53.Jaka jest najmniejsza ilość krawędzi w grafie o n- wierzch.ch.
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 wierzch. 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- wierzch. 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 wierzch. 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 wierzch., 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 wierzch. 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ąć wierzch. tych krawędzi wtedy k-1<k albo graf ten będzie spójny i usuwam wtedy wierzch. i mamy graf niespójny).????
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={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, wierzch..
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 t,że an≠bn to każdy wierzch. vi jest indukowany k krawędziami to G- k-regularny. Ilość wierzch. 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ść 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 wierzch. możemy podzielić więc na dwie klasy G1 i G2 rozdzielne, czyli t,że żaden wierzch. należący do G1 nie sąsiaduje z żadnym wierzch. należącym do G2. Jeżeli teraz weźmiemy dopG to wszystkie wierzch. z klasy G1 sąsiadują ze wszystkimi wierzch. 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 wierzch. w dopG istnieje droga ⇒ dopG jest spójny. Analogicznie w drugą stronę.
61. Ile jest liści w drzewie T, które ma n wierzch. stopnia i i=1,2...m= max deg v
Drzewo jest to graf spójny acykliczny o |V|=|E|+1 wierzch.; ni wierzch. 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 wierzch. izolowanych, czyli stopnia 0. Skoro drzewo to graf spójny to wierzch. 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 ton1=2+n3 m=4 to n1=2+n3+2n4 liści w drzewie jest conajmniej 2
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. (Zasada szufladkowa)
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°.
73.Graf Kn ma nn-2 drzew spinających.
Każdemu drzewu oznakowanemu mającemu n wierzch. 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 wierzch..
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 wierzch. stopnia nieparzystego jest parzysta.
Przypomnijmy, że z lematu o uściskach dłoni, dla dowolnego grafu G=(V,E) ∑δv=2|E| (δ-stopień wierzch.), 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 wierzch. 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 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ównoważne ze znalezieniem cyklu Ham..
69.Pokazać, że jeżeli G jest grafem o nieparzystej liczbie wierzch., 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 wierzch., 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 wierzch. 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.
74.Wykaż, że dla każdej liczby naturalnej n, graf związany z alkoholem CnH2n+1OH jest drzewem (wierzch. odpowiadający atomowi tlenu ma stopień 2).
Ten graf jest grafem spójnym mającym n+(2n+1)+1+1=3n+3 wierzch. 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 wierzch.
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 wierzch. będą reprezentować osoby i dwa wierzch. 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 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 osoby odpowiadające wierzch. w i x znają się, to wierzch. v, w i x tworzą trójkąt narysowany linią ciągłą, co zakończy dowód. Podobnie, jeśli osoby odpowiadające wierzch. w i y lub wierzch. 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 wierzch. w, x i y nie znają się, to wierzch. 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 wierzch. na dwa zbiory rozłączne A i B w taki sposób, by każda krawędź grafu G łączyła wierzch. ze zbioru A z wierzch. 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ż wierzch. vm musi należeć do B, cykl ma długość parzystą.
72.Udowodnij, że jeśli w grafie G każdy wierzch. 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 wierzch. grafu G. Tworzymy trasę vv1v2… przez indukcję, wybierając jako v1 dowolny wierzch. sąsiadujący z v, a następnie, ∀i>1 wybierając jako wierzch. vi+1 dowolny wierzch. sąsiadujący z vi, różny od vi-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 vk jest pierwszym takim wierzch., to część trasy znajdująca się między pierwszym i drugim wystąpieniem wierzch. vk jest szukanym cyklem.
75.Niech G będzie grafem prostym, mającym n wierzch.. 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 wierzch., 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 wierzch., 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 wierzch., to całkowita liczba wierzch. 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 wierzch. i z k-1 wierzch. izolowanych. Stąd wynika teza twierdzenia. Wniosek: Każdy graf prosty, który ma n wierzch. 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 wierzch. nieparzystego wierzch. (Tw. G jest eulerowski ⇔ każdy wierzch. 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 wierzch.ch.
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 wierzch. 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 wierzch. 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 wierzch. brakuje jednego koloru, a ponadto każdy z n-1 kolorów jest brakującym przy dokładnie jednym z wierzch.. Dodajmy n-ty wierzch. i połączmy go krawędzią po kolei z każdym z n-1 pozostałych wierzch.. Pokolorujemy te krawędzie, używając każdorazowo brakującego przy danym wierzch. 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.
83.Jeśli G jest grafem prostym, w którym największy stopień wierzch. jest Δ, χ(G)=Δ+1.
Indukcja względem liczby wierzch. grafu G. Niech G będzie grafem prostym mającym n wierzch.. Jeśli usuniemy z niego dowolny wierzch. v wraz z krawędziami incydentnymi z nim, to otrzymany graf będzie również grafem prostym, który będzie miał n-1 wierzch. oraz największy stopień wierzch. 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 wierzch. sąsiadujących z v.
80.Niech (V1,V2,E) będzie grafem dwudzielnym o największym stopniu wierzch. = d. Wówczas χ'(G)=d.
Zastosujemy metodę indukcji względem |E|. Załóżmy, że G ma |E|>0, jego największy stopień wierzch. 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ń wierzch. 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 wierzch.ch 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 wierzch. v i w użyliśmy wszystkich kolorów. Ponieważ w G' stopnie wierzch. 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 wierzch. 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 wierzch. 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 wierzch. w nie jest wierzch. 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 wierzch.ch 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ń wierzch. 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 wierzch. 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ń wierzch. 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 wierzch. v1,…,vr jest ≤d-1, a mamy do dyspozycji d+1 kolorów. W ten sposób dla każdego wierzch. vi istnieją co najmniej dwa kolory, które przy nim nie występują, a więc nie występują one również przy obu wierzch.ch 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 wierzch. stopnia nieparzystego, ma drogę Eulera.
Przypuśćmy, że u i v są wierzch.mi stopni nieparzystych. Utwórzmy nową krawędź e, łączącą je. Wtedy graf G∪{e} ma wszystkie wierzch. stopni parzystych, a więc ma cykl Eulera bo graf spójny, w którym każdy wierzch. ma stopień parzysty ma cykl Eulera. Usuńmy znowu krawędź e. To, co pozostanie z cylku Eulera, jest drogą Eulera w grafie G.
84.Każdy planarny graf prosty zawiera wierzch. stopnia co najwyżej 5.
Załóżmy, że nasz graf jest spójny i ma co najmniej 3 wierzch.. Gdyby każdy wierzch. 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ę wierzch.. Przypuśćmy, że G jest planarnym grafem prostym mającym n wierzch. i że wszystkie planarne grafy proste mające n-1 wierzch. są 6 - kolorowalne. G ma wierzch. v stopnia co najwyżej 5. Jeśli usuniemy wierzch. v wraz z wszystkimi krawędziami z nim incydentnymi, to otrzymany graf będzie miał n-1 wierzch., a więc będzie 6 - kolorowalny. RYS. Wtedy 6 - kolorowanie grafu G otrzymujemy, kolorując wierzch. v kolorem różnym od kolorów wierzch. sąsiadujących.
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.
62 (z 66). G dwuspójny, to każde dwie sąsiednie krawędzie leżą na pewnym 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 l1 i l2 RYS2..
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=(S1,...,Sn), gdzie Si 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 Si 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 Si.
86. Niech G będzie rysunkiem płaskim spójnego grafu płaskiego i niech n, m i f oznaczają odpowiednio liczbę wierzchołków, krawędzi i regionów grafu G. Wtedy n-m+f=2
Indukcja względem liczby krawędzi. Jeśli m=0, to n=1(gdyż graf G jest spójny) oraz f=1. W tym przypadku tw. jest prawdziwe. Przypuśćmy teraz, że tw. jest prawdziwe dla wszystkich grafów mających co najwyżej m-1 krawędzi i niech G będzie grafem mającym krawędzi. Jeśli graf G jest drzewem, to m=n-1 i f=1, a więc rzeczywiście n-m+f=2. Jeśli graf G nie jest drzewem, to niech e będzie dowolną krawędzią jakiegoś cyklu w G. Wtedy graf G-e jest spójnym grafem planarnym, mającym n wierzchołków, m-1 krawędzi i f-1 ścian, a więc z założenia indukcyjnego wynika, że zachodzi równość n-(m-1)+(f-1)=2. Stąd wynika, że n-m+f=2.