[PDF] [PDF] Graph Theory The length of a path

View - Download [PDF] Graph Theory

Previous PDF

Next PDF

Graph Theory

Lecture by Prof. Dr. Maria Axenovich

Lecture notes by Monika Csikos, Daniel Hoske and Torsten Ueckerdt 1

Contents

1 Preliminaries

4

2 Matchings

17

3 Connectivity

25

4 Planar graphs

36

5 Colorings

52

6 Extremal graph theory

64

7 Ramsey theory

75

8 Flows

86

9 Random graphs

93

10 Hamiltonian cycles

99

References

101

Index102

2

Introduction

These notes include major denitions, theorems, and proofs for the graph theory course given by Prof. Maria Axenovich at KIT during the winter term 2019/20. Most of the content is based on the book \Graph Theory" by Reinhard Diestel [4]. A free version of the book is available athttp://diestel-graph-theory.com.

Conventions:

G= (V;E) is an arbitrary (undirected, simple) graph n:=jVjis its number of vertices m:=jEjis its number of edges

Notationnotation denition meaning

V k,Vnite set, kintegerfSV:jSj=kgthe set of allk-element subsets ofV V

2,Vnite setf(u;v) :u;v2V; u6=vgthe set of all ordered pairs

of elements inV [n],nintegerf1;:::;ngthe set of the rstnposi- tive integers

N1;2;:::the natural numbers, not

including 0 2

S,Snite setfT:TSgthe power set ofS, i.e.,

the set of all subsets ofS S4T,S,Tnite sets (S[T)n(S\T) the symmetric dierence of setsSandT, i.e., the set of elements that ap- pear in exactly one ofS orT A _[B,A,Bdisjoint setsA[Bthe disjoint union ofA andB3

1 Preliminaries

Denition 1.1.Agraph,GgraphGis an ordered pair (V;E), whereVis a nite set and EV

2is a set of pairs of elements inV.

The setVis called the set ofvertex, edgeverticesandEis called the set ofedgesofG.

The edgee=fu;vg 2V

2is also denoted bye=uv.

Ife=uv2Eis an edge ofG, thenuis calledadjacent, incidentadjacenttovanduis called incidenttoe. Ife1ande2are two edges ofG, thene1ande2are calledadjacentife1\e26=;,

i.e., the two edges are incident to the same vertex inG.We can visualize graphsG= (V;E) using pictures. For each vertexv2Vwe draw a

point (or small disc) in the plane. And for each edgeuv2Ewe draw a continuous curve starting and ending in the point/disc foruandv, respectively. Several examples of graphs and their corresponding pictures follow:

V= [5],E=f12;13;24g

V=fA;B;C;D;Eg,

E=fAB;AC;AD;AE;CEg

Denition 1.2(Graph variants).

Adirected graphdirected graphis a pairG= (V;A) whereVis a nite set andAV2. The edges of a directed graph are also calledarcsarc. Amultigraphmultigraphis a pairG= (V;E) whereVis a nite set andEis a multiset of elements fromV 1[V

2, i.e., we also allow loops and multiedges.

Ahypergraphhypergraphis a pairH= (X;E) whereXis a nite set andE2Xn f;g.Denition.For two graphsG1= (V1;E1) andG2= (V2;E2) we say thatG1and

G

2areisomorphicisomorphic,', denoted byG1'G2, if there exists a bijection:V1!V2with

xy2E1if and only if(x)(y)2E2. Loosely speaking,G1andG2are isomorphic if they are the same up to renaming of vertices. When making structural comments, we do not normally distinguish between isomor- phic graphs. Hence, we usually writeG1=G2=instead ofG1'G2whenever vertices 4 are indistinguishable. Then we use the informal expressionunlabeled graphunlabeled graph(or just graphwhen it is clear from the context) to mean an isomorphism class of graphs.

Important graphs and graph classes

Denition.For all natural numbersnwe dene:

thecomplete graphcomplete graph, K nK nonnvertices as the (unlabeled) graph isomorphic to [n];[n] 2

. We also call complete graphscliques.forn3, thecyclecycle,CnCnonnvertices as the (unlabeled) graph isomorphic to[n];fi;i+ 1g:i= 1;:::;n1[n;1. Thelength of a cycleis its number

of edges. We writeCn= 12:::n1. The cycle of length 3 is also called atriangletriangle. thepathpath,PnPnonnvertices as the (unlabeled) graph isomorphic to[n];fi;i+1g: i= 1;:::;n1. The vertices 1 andnare called theendpointsorendsof the path. Thelength of a pathis its number of edges. We writePn= 12:::n. theempty graphempty graph,EnEnonnvertices as the (unlabeled) graph isomorphic to[n];;.

Empty graphs correspond to independent sets.

5 form1, thecomplete bipartite graphcomplete bipartite graph,Km;nK m;nonn+mvertices as the (unlabeled) graph isomorphic to (A[B;fxy:x2A;y2Bg), wherejAj=mandjBj=n,

A\B=;.

forr2, acompleter-partitecompleter-partitegraph as an (unlabeled) graph isomorphic to

A1_[_[Ar;fxy:x2Ai;y2Aj;i6=jg;

whereA1;:::;Arare non-empty nite sets. In particular, the complete bipartite graphKm;nis a complete 2-partite graph. thePetersen graphPetersen graphas the (unlabeled) graph isomorphic to [5] 2 ;fS;Tg:S;T2[5] 2 ;S\T=; :for a natural numberk,kn, theKneser graphKneser graph,

K(n;k)K(n;k) as the (unlabeled)

graph isomorphic to [n] k fS;Tg:S;T2[n] k ;S\T=;

Note thatK(5;2) is the Petersen graph.

6

Corollary 14.Ak-regular bipartite graph has a properk-edge-coloring.Theorem 2.3(K}onig's Theorem).LetGbe bipartite. Then the size of a largest

matching is the same as the size of a smallest vertex cover.Proof.Letcbe the vertex-cover number ofGandmbe the size of a largest matching

ofG. Since a vertex cover should contain at least one vertex from each matching edge, cm. Now, we shall prove thatcm. LetMbe a largest matching inG, we need to show thatc jMj. LetAandBbe the partite sets ofG. Analternating pathis a path that starts with a vertex inAnot incident to an edge ofM, and alternates between edges not inMand edges inM. Note that if an alternating path must end in a vertex saturated byM, otherwise one can nd a larger matching. Let U

0=fb:ab2E(M) for somea2Aand some alternating path ends inbg;

U=U0[ fa:ab2E(M);b62U0g:

We see thatjUj=m. We shall show thatUis a vertex cover, i.e. that every edge ofGcontains a vertex fromU. Indeed, ifab2E(M), then eitheraorbis inU. If ab62E(M), we consider the following cases:

Case 0:a2U. We are done.

Case 1:ais not incident toM. Thenabis an alternating path. Ifbis also not incident toMthenM[fabgis a larger matching, a contradiction. Thusbis incident toMand thenb2U. Case 2:ais incident toM. Thenab02E(M) for someb0. Sincea62U, we have that b

02U, thus there is an alternating pathPending inb0. IfPcontainsb, thenb2U,

otherwisePb0abis an alternating path ending inb, sob2U.Assume that each vertex in a complete bipartite graphG= (A[B;E) gives an ordering

or a ranking to its neighbors, and writey xy0. If we assume for simplicity thatAis a set of women andBis a set of men, then a stable matching is thought of 19 as a set of \stable" marriages. I.e., for any "marriage" fromM, one of the spouses \has no reason to leave". Gale and Shapley proved in 1962 that there is always a stable matching in a bipar- tite graph equipped with a ranking of the neighbors for each vertex. They gave an algorithm to nd one. The algorithm is as follows: Initially, no one is engaged. During each round, each man who is not engaged proposes to highest on his list woman who did not reject him yet; for a woman receiving multiple proposals, she says "maybe" to the highest ranked oer and rejects other proposals, the man to whom she said "maybe" is now engaged to her, the rejected men are not engaged anymore. The rounds repeat until everybody is engaged. \ Everyone gets married": At the end, there cannot be a man and a woman both unengaged, as he must have proposed to her at some point (since a man will eventually propose to everyone, if necessary) and, being proposed to, she would necessarily be engaged (to someone) thereafter. \The marriages are stable": Let Alice and Bob both be engaged, but not to each other. Upon completion of the algorithm, it is not possible for both Alice and Bob to prefer each other over their current partners. If Bob prefers Alice to his current partner, he must have proposed to Alice before he proposed to his current partner. If Alice accepted his proposal, yet is not married to him at the end, she must have dumped him for someone she likes more, and therefore doesn't like Bob more than her current partner. If Alice rejected his proposal, she was already with someone she liked more than Bob. " Wikipedia20 For any graphHdeneq(H) to be the number of odd components ofH, i.e., the number of connected components ofHconsisting of an odd number of vertices. Theorem 2.4(Tutte's Theorem, 2.2.1).A graphGhas a perfect matching if and only ifq(GS) jSjfor allSV.Proof.Assume rst thatGhas a perfect matchingM. Consider a setSof vertices and an odd componentG0ofGS. We see that there is at least one vertex inG0 that is incident to an edge ofMthat has another endpoint not inG0. This endpoint

must be inS. ThusjSjis at least as large as the number of odd components.Now, assume thatq(GS) jSjfor allSV. Assume thatGhas no perfect

matching andjV(G)j=n. Note thatjV(G)jis even (it follows from the assumption q(GS) jSjapplied toS=;). LetG0be constructed fromGby adding missing edges as long as no perfect matching appears. LetSbe a set of vertices of degree n1. Note that it could be empty. Claim 1.Each component ofG0Sis complete. Assume not, there is a component Fcontaining verticesa;b;csuch thatab;bc2E(G0) andac62E(G0). Sinceb62S, deg(b)< n1, so there isd2V(G),d62 fa;b;cg, such thatbd62E(G0). By maximality ofG0,G0[achas a perfect matchingM1andG0[bdhas a perfect matchingM2. Let

Hbe a graph with edge setE(M1)E(M2).21

ThenHis a vertex-disjoint union of even cycles, alternating edges fromM1andM2. We have thatac;bd2E(H). Ifacandbdare in the same cycleCofH, we see that C[fab;cbghas a perfect matchingMCnot containing eitheracorbd. Build a perfect matchingMofG0fromMC, a perfect matchings of other components ofH, and the edges ofM1\M2.Ifacandbdbelong to dierent cycles ofH, again build a perfect matchingMofG0 not containingacand not containingbd. We see thatMis a perfect matching ofG0, contradicting the assumption thatG0has no perfect matching. This proves Claim 1.Claim 2.q(G0S)>jSj. Ifq(G0S) jSj, build a perfect matching ofG0by matching a single vertex in each odd component ofG0StoS, matching the remaining vertices in each component of G

0Sto the vertices in respective components, and matching the remaining vertices

ofSto the vertices ofS. SinceV(G0) is even, we can construct a perfect matching in this way, a contradiction. This proves Claim 2.22 Finally, observe that sinceG0is obtained fromGby adding edgesq(GS)q(G0S). Thusq(GS)>jSj, a contradiction.Denition 2.5.LetG= (V;E) be any graph. For all functionsf:V!N[ f0ganf-factor ofGf-factoris a spanning subgraphH ofGsuch that degH(v) =f(v) for allv2V. Letf:V!N[ f0gbe a function withf(v)deg(v) for allv2V. We can construct the auxiliary graphT(G;f)T(G;f)by replacing each vertexvwith vertex sets A(v)[B(v) such thatjA(v)j= deg(v) andjB(v)j= deg(v)f(v). For adjacent verticesuandvwe place an edge betweenA(u) andA(v) such that the edges between theA-sets are independent. We also insert a complete bipartite graph

betweenA(v) andB(v) for each vertexv.LetHbe a graph. AnH-factor ofGH-factoris a spanning subgraph ofGthat is a

vertex-disjoint union of copies ofH, i.e., a set of disjoint copies ofHinGwhose vertex sets form a partition ofV.23 Lemma 15.Letf:V!N[ f0gbe a function withf(v)deg(v) for allv2V. ThenGhas anf-factor if and only ifT(G;f) has a 1-factor. Proof.Assume rst thatGhas anf-factor. For each edgeuvof thef-factor, consider an edge betweenA(u) andA(v) such that respective edges form a matching,M. We see that exactlyf(v) vertices ofA(v) are saturated byM. Build a matching between the unsaturated byMvertices ofA(v) andB(v), for eachv2V(G). Assume thatT(G;f) has a perfect matchingM. Delete allB(v)'s,v2V(G), and contractA(v) into a single vertexv. After such an operation applied toM, each vertex

vhas degreef(v) and the graph is clearly a subgraph ofG.Theorem 16(Hajnal and Szemeredi 1970).IfGsatises(G)(11=k)n, where

kis a divisor ofn, thenGhas aKk-factor. Theorem 17(Alon and Yuster 1995).LetHbe a graph. IfGsatises (G) 11(H) n; thenGcontains at least1o(1)n=jV(H)jvertex-disjoint copies ofH. Theorem 18(Komlos, Sarkozy, and Szemeredi 2001).For any graphHwith(H) = k,jHj=r, there are constantsc;n0such that for anynn0such thatnis divisible byrand(G)(11=k)n+c,Gcontains anH-factor. Theorem 19(Wang 2010).IfjGj= 4mand(G)n=2, thenGhas aC4-factor. Denition.For a graphH, dene thecritical chromatic number ofHcritical chromatic number,cr(H)as cr(H) =((H)1)jHjjHj (H); where(H) denotes the minimum size of the smallest color class in a coloring ofH with(H) colors.

Note that for any graphH,cr(H) always satises

(H)1cr(H)(H) andcr(H) =(H) if and only if for every coloring ofHwith(H) colors, all of the color classes have equal size. Theorem 20(Kuhn and Osthus, 2009).LetHbe a graph andn2Nso thatnis divisible byjHjand dene (n;H) = minfk: anyGwithjGj=n; (G)khas anH-factorg:

Then there exists a constantC=C(H) so that

11r n1(n;H) 11r n+C; wherer2 f(H);cr(H)g. 24

3 Connectivity

Denition 3.1.

For a natural numberk1, a graphGis calledk-connectedk-connectedifjV(G)j k+ 1 and for any setUofk1 vertices inGthe graphGUis connected. In particular,Knis (n1)-connected. The maximumkfor whichGisk-connected is called theconnectivity ofGconnectivity,(G), denoted by(G). For example,(Cn) = 2 and(Kn;m) = minfm;ng: For a natural numberk1, a graphGis calledk-linkedk-linkedifjGj 2kand for any 2kdistinct verticess1;s2;:::;sk;t1;t2;:::;tkthere are vertex-disjointsi-ti- paths,i= 1;:::;k.For a graphG= (V;E) a setXV[Eof vertices and edges ofGis called acut setcut setofGifGXhas more connected components thanG. If a cut set consists of a single vertexv, thenvis called acut vertexcut vertexofG; if it consists of a single edgee, theneis called acut edge or bridgecut edge, bridgeofG. For a natural number`1, a graphGis called`-edge-connected`-edge-connectedifGis non- trivial and for any setFEof fewer than`edges inGthe graphGFis connected.

Theedge-connectivity ofGedge-connectivity,

0(G)is the maximum`such thatGis`-edge-connected.

It is denoted by0(G) .

Gnon-trivial tree)0(G) = 1,Gcycle)0(G) = 2:Clearly, for everyk;`2, if a graph isk-connected,k-linked or`-edge-connected,

then it is also (k1)-connected, (k1)-linked or (`1)-edge-connected, respectively. Moreover, for a non-trivial graph is it equivalent to be 1-connected, 1-linked, 1-edge- connected, or connected. 25
Lemma 3.2.For any connected, non-trivial graphGwe have (G)0(G)(G):Proof.Observe rst that for a complete graphG=Kn,(G) =0(G) =(G) =n1.

So, we can assume thatGis not complete.

To show that0(G)(G), observe thatGcan be disconnected by removing the edges incident to a vertexvof minimum degree. To show that(G)0(G), consider a smallest separating set of edges,F, of size0(G). We shall show that(G) jFj. Case 1.There is a vertexvnot incident toF. Thenvis in the componentG0of GF. Then the vertices ofG0incident toFseparateG, there are at mostjFjof them. Case 2.Every vertex is incident toF. Letvbe a vertex of degree less thanjGj 1. Such exists sinceGis not complete. LetG0be the component ofGFcontaining v. ThenU=fu:u2N(v);uv62Fg V(G0). For eachu2U,uis incident toF, moreover distinctu's fromUare incident to distinct edges fromF. So,jN(v)j jFj.

We see thatN(v) is a separating set, so(G) jFj.Example.A graphGwith(G);0(G)(G).Denition.For a subsetXof vertices and edges ofGand two vertex setsA;BinG

we say thatXseparatesAandBseparateif eachA-B-path contains an element ofX.

Note that ifXseparatesAandB, then necessarilyA\BX.Some sets separatingAandB:fe1;e4;e5g,fe1;u2g,fu1;u3;v3g

26
Lemma 39.LetXbe a 3-connected graph,Gbe edge-maximal with respect to not containingTX. LetSbe a vertex cut ofG,jSj 2. ThenG=G1[G2, V(G1)\V(G2) =S,Giis edge-maximal withoutTXandSinduces an edge. Proof.IfjSj= 0, add an edge between two components. IfS=fvg, letvi2N(v)\V(Gi),i= 1;2. ConsiderH=TXinG+v1v2. All branch vertices ofHmust be in eitherG1orG2, assume without loss of generality inG1. Then we see thatG1containsTXby replacing a path ofHwithvv1if needed. IfS=fx;yg, assume thatxandyare not adjacent. ConsiderH=TXInG+xy. Again, all branch vertices ofHare without loss of generality inG1. Moreoverxy2 E(H). Replacexywith a path inG2to obtain a copy ofTXinG. This a contradiction, soxyis an edge inG. To show thatG1is edge-maximal with respect to not containing TX, considerH=TXinG+uv,u;v2V(G1). All branch vertices ofHis either in G

2or inG1. If they all are inG2, replace a path ofHthroughuvwith one throughxy.

This results inTXinG2, a contradiction. Thus, all branch vertices ofHare inG1. Replacing a path ofHthat is inG2withxyif needed, we see thatTXG1+fuvg. This shows the maximality ofG1with respect to not containingTX. 43
Lemma 40.LetjGj 4 andGis edge maximal with respect to not containingTK5 orTK3;3. ThenGis 3-connected. Proof.We use induction onjGj. We are done ifjGj= 4. Assume thatjGj>4. Assume thatGsatises the conditions of the lemma but is not 3-connected, i.e., it contains a vertex cutS=fx;yg. LetG=G1[G2,V(G1)\V(G2) =S. We have thatTK56Gi,TK3;36Gi, andjGij37 thatMK56GiandMK3;36Gi,i= 1;2. SinceMK56GiandMK3;36Gi, i= 1;2 andGi's are 3-connected orK3, we have by Lemma 38Gi's are planar. We have thatxy2E(G) by Lemma 39. Consider embeddings ofG1andG2so thatxyis on the boundary of unbounded face. Letzi2Gi,i= 1;2,zi62 fx;ygon the boundary of the respective unbounded face. ThenG+fz1z2gcontains a subgraphHthat isTK5orTK3;3. Case 1. The branch vertices ofHare inGi, sayi= 1. Ifxz1;yz12E(G1),G1contains TK

5orTK3;3.

Ifxz162E(G1) thenG1+xz1containsTK5orTK3;3. Ifyz162E(G1) thenG1+ yz

1containsTK5orTK3;3. However,G1+xz1;G1+yz1, andG1are planar, a

contradiction. 44
Case 2. There are branch vertices ofHinG1nG2and inG2nG1. LetWibe the set of branch vertices ofHinV(Gi),i= 1;2. Since there are at most 2 independent paths betweenwi2Wiandwj2Wj, we see thatH6=TK5. So,H=TK3;3. We see that eitherjW1\V(G1G2)j= 1 or jW2\V(G2G1)j= 1. Assume thatjW2\V(G2G1)j= 1 and letv=W2\V(G2G1). ThenG0=G1+fvg+fvx;vy;vz1gcontainsTK3;3. ButG0is planar, a contradiction. 45

Proof of Kuratowski's theorem

Theorem 4.5(Kuratowski's Theorem).The following statements are equivalent for graphsG: i)Gis planar; ii)Gdoes not haveK5orK3;3as minors;

iii)Gdoes not haveK5orK3;3as topological minors.Proof.The equivalence of ii) and iii) follows from Lemma 37.

Assume i). Note thatK5is not planar since 10 =jjK5jj>3jK5j6 = 9, violating the Euler's formula. AdditionallyK3;3is not planar since 9 =jjK3;3jj>2jK3;3j4 = 8, vi- olating the Euler's formula for triangle-free graphs. SinceK5andK3;3are not planar, TK

5andTK3;3are not planar, otherwise one can create and embedding ofK5from

one ofTK5by \merging" the edges resulted from subdivisions. Similarly,TK3;3is not planar, soGdoes not containTK5andGdoes not containTK3;3. This implies iii). We only need to show that ii) implies i). LetGbe a graph that contains neitherMK5 norMK3;3. Add as many edges as possible to preserve this property, let the resulting graph beG0. By Lemmas 37 and 40,G0is 3-connected. Lemma 38 states thatG0is planar. Thus a subgraphGofG0is planar. This implies i).Denition 4.6. LetXbe a set and X2be a relation onX, i.e.,is a subset of all ordered pairs of elements inX. Thenis apartial orderpartial orderif it is re exive, antisymmetric and transitive. A partial order istotaltotal orderifxyoryxfor everyx;y2X. Letbe a partial order on a setX. The pair (X;) is called aposetposet(partially ordered set). Ifis clear from context, the setXitself is called a poset. The poset dimension of(X;)poset dimension, dim(X;)is the smallest numberdsuch that there are total ordersR1;:::;RdonXwith=R1\ \Rd. dim() = 1, dim(xy) = 2 sincexy=yx\xy Theincidence poset(V[E;)incidence poseton a graphG= (V;E) is given byveif and only ifeis incident tovfor allv2Vande2E. 46
Theorem 41(Schnyder).LetGbe a graph andPbe its incidence poset. ThenGis planar if and only if dim(P)3.

Theorem 4.7(5-Color Theorem, 5.1.2).Every planar graph is 5-colorable.Proof.We shall apply induction onjV(G)jwith a trivial basis whenjV(G)j 5.

Assume thatjV(G)j>5, assume further thatGis maximally planar, i.e., it has a plane embedding that is a triangulation. By Euler's formula, there is a vertexvof degree at most 5. By induction, there is a proper coloringcofGvin at most 5 colors from [5]. Ifcassigns at most 4 colors toN(v), we can assignva color from [5] not used inN(v). Otherwise, assume w.l.o.g. thatN(v) =fv1;v2;v3;v4;v5g,c(vi) =i, andvi's are cyclically arranged on the face ofGv. Letc0be a coloring obtained by

1;3 switch atv1. Ifc0(v1) = 3 andc0(v3) = 3, thenc0does not use color 1 onN(v) and

we can colorvwith 1. So, there is av1-v3-path colored 1 and 3 inc. Similarly, there is av2-v4-path colored 2 and 4 inc. However, this is impossible since these paths must cross is a vertex and this vertex should have a color inf1;3g \ f2;4g. The more well-known 4-coloring theorem is much harder to prove.

Wrong proof of Four Color Theorem by Kempe

Consider a graphGand a proper vertex coloringcusing colors from [k]. For a vertexv of colori, we say that a coloringc0is obtained fromcby ani;jcolor switch atvif the colorsiandjare switched in the maximal connected subgraph ofGthat is induced by vertices of coloriandjand containv. The idea of Kempe was to prove a Four-Color theorem using color switches and induc- tion on the number of vertices as follows. Consider a planar graph onnvertices. If n4, the graph is four-colorable. Assume thatn >4 and that each planar graph on less thannvertices is 4-colorable. By Euler's formula there is a vertex,v, of degree at most 5. Letcbe a proper coloring ofG0=Gvwith at most four colors from [4]. If the number of colors used onN(v) is at most 3, we see thatvcould be colored with a color from [4] not used on its neighbors. Thus we can assume that the degree ofvis 4 or 5 and all four colors are present onN(v). If degree ofvis 4, assume that the colors 47

1;2;3;4 appear cyclically onN(v) on verticesv1;v2;v3;v4respectively. First, apply

1;3 color switch atv1. If during this switch the color ofv3remain 3, we can colorv

with color 1. Thus, there is av1-v3-path colored only with 1 and 3. Similarly there is av2-v4-path colored with 2 and 4 only. However these paths cross, a contradiction. Therefore one of these 1-3 or 2-4 switches results in the neighborhood ofvhaving only three colors and thusvcould be colored with the fourth color. Now, assume that degree ofvis 5 and the neighbors are colored 1;2;3;4;2, on verticesv1;:::;v5 respectively. As before we can assume that there is av1-v3-path colored with 1 and

3 and av1-v4-path colored with 1 and 4. Then, we could do 2-3-switch atv4and

2-4-switch atv2that results inN(v) loosing color 2. Thus we can colorvwith 2.

However, there is a problem, see gure. The 2-3 and 2-4 switches resulted in two adjacent verticesuandwof color 2. This mistake was found in 1890 by P. Heawood, after the conjecture was published by De Morgan in 1860, and "proved" by A. Kempe in 1878 (published in Nature). Interestingly, it is one of the rst theorems that has been proved using computer assistance. The computer-generated proof uses an enormous case distinction. Some mathematicians have philosophical problems with this approach since the resulting proof cannot be easily veried by humans. A shorter proof is still outstanding. Theorem 4.8(Appel and Haken, 1976).Every planar graph is 4-colorable.Denition 4.9. LetL(v)Nbe a list of colors for each vertexv2V. We say thatGisL-list- colorable L-list-colorableif there is coloringc:V!Nsuch thatc(v)2L(v) for eachv2Vand adjacent vertices receive dierent colors. Letk2N. We say thatGisk-list-colorable ork-choosablek-list-colorableifGisL-list-colorable for each listLwithjL(v)j=kfor allv2V.

Thechoosabilitychoosability,

ch(G), denoted by ch(G), is the smallestksuch thatGisk-choosable.

Theedge choosabilityedge choosability,

ch

0(G), denoted by ch0(G), is dened analogously.48

We say that a plane graph isouter triangulationif it has all triangular inner faces and an outer face forming a cycle. Theorem 4.10(5-List-Color Theorem).LetGbe a planar graph. Then the list

chromatic number ofGis at most 5.Proof.We shall prove a stronger statement (?): LetGbe an outer triangulation with

two adjacent verticesx;yon the boundary of the outer face. LetL:V(G)!2Nbe a list assignment such thatjL(x)j=jL(y)j= 1,L(x)6=L(y),jL(z)j= 3 for all other vertices on unbounded face, andjL(z)j= 5 for all vertices not on unbounded face.

ThenGisL-colorable.

We shall prove (?) by induction onjV(G)jwith an obvious basis forjV(G)j= 3. Consider an outer triangulationGon more than 3 vertices. Case 1.There is a chord, i.e., an edgeuvjoining two non-consecutive vertices of the outer face. ThenG=G1[G2, such thatfu;vg=V(G1)\V(G2),jGj>jGij 3, G iis an outer triangulation,i= 1;2. Without loss of generality,x;yare on the outer face ofG1. Apply induction toG1to obtain a properL-coloringc0ofG1. Next apply induction toG2withuandvplaying a role ofxandyand list assignmentsL0such thatL0(u) =fc0(u)g,L0(v) =fc0(v)g,L0(z) =L(z), forz62 fx;yg. Then there is a properL0-coloringc00ofG2. Since these colorings coincide onuandv, together they form a proper coloringcofG, i.e.,c(v) =c0(v) forv2V(G1) andc(v) =c00(v) for v2V(G2). Case 2.There is no chord, i.e. Case 1. does not hold. Letzbe a neighbor ofx on the boundary of outer face,z6=y. LetZbe the set of neighbors ofznot on the outer face. LetL(x) =fag,L(y) =fbg. Letc;d2L(z) such thatc6=aandd6=a. LetG0=Gz. LetL0be list assignment forV(G0) such thatL0(v) =L(v) fc;dg, forv2ZandL0(v) =L(v) forv62Z. By inductionG0has a properL0-coloringc0. We shall extend a coloringc0to a coloringcorG, i.e., we letc(v) =c0(v) ifv6=z. We shall giveza colorcord. Specically, letc(z)2 fc;dg n fc0(q)g, whereqis the neighbor ofzon outer face, not equal tox. We see then thatzhas a color dierent from the color of each of its neighbors. Thuscis a properL-coloring. 49
Figure 2:A construction b yMizrakhani of a non -4-choosableplanar graph. 50
An embedding of a graph on a surface is 2-cellif for each region and each simple closed curve in the region contracts continuously to a point. Euler formula states that ne+f= 22 , wherene+fis called Euler's characteristic, and 2 is Euler's genus. For orientable surfaces corresponds to the number of handles. Theorem 42(Heawood formula, 1890 (Weisstein, Ringel 1968, 1974)).LetGbe embeddable to a surfaceSwith Euler characteristic 22quotesdbs_dbs19.pdfusesText_25

[PDF] how to find number of vertices in a graph

[PDF] how to find nyquist rate

[PDF] how to find old obituaries in alabama

[PDF] how to find out if someone died in germany

[PDF] how to find regression equation on excel

[PDF] how to find relevant case law

[PDF] how to find slope on desmos

[PDF] how to find the discriminant

[PDF] how to find the imaginary roots of a polynomial

[PDF] how to find the issue in an argument

[PDF] how to find the volume of a triangular prism

[PDF] how to fix missing font in adobe

[PDF] how to forecast exchange rates in excel

[PDF] how to format a title page in word

[PDF] how to format a word document to look professional