Graph Theory - KIT

1 Graph TheoryLecture by Prof. Dr. Maria AxenovichLecture notes by M onika Csik os, Daniel Hoske and Torsten Ueckerdt1 Contents1 Preliminaries42 Matchings173 Connectivity254 Planar graphs365 Colorings526 Extremal Graph theory647 Ramsey theory758 Flows869 Random graphs9310 Hamiltonian cycles99 References101 Index1022 IntroductionThese notes include major definitions, theorems, and proofs for the Graph Theory coursegiven by Prof. Maria Axenovich at KIT during the winter term 2019/20. Most of thecontent is based on the book Graph Theory by Reinhard Diestel [4]. A free versionof the book is available : G= (V,E) is an arbitrary (undirected, simple) Graph n:=|V|is its number of vertices m:=|E|is its number of edgesNotationnotationdefinitionmeaning(V k),Vfinite set,kinteger{S V:|S|=k}the set of allk-elementsubsets ofVV2,Vfinite set{(u,v) :u,v V, u6=v}the set of all ordered pairsof elements inV[n],ninteger{1.}

2 ,n}the set of the firstnposi-tive integersN1,2,..the natural numbers, notincluding 02S,Sfinite set{T:T S}the power set ofS, ,the set of all subsets ofSS4T,S,Tfinite sets(S T)\(S T)the symmetric differenceof setsSandT, , theset of elements that ap-pear in exactly one ofSorTA B,A,Bdisjoint setsA Bthe disjoint union ofAandB31 PreliminariesDefinition ,GgraphGis an ordered pair (V,E), whereVis a finite set andE (V2)is a set of pairs of elements inV. The setVis called the set ofvertex, edgeverticesandEis called the set ofedgesofG. The edgee={u,v} (V2)is also denoted bye=uv. Ife=uv Eis an edge ofG, thenuis calledadjacent, incidentadjacenttovanduis calledincidenttoe. Ife1ande2are two edges ofG, thene1ande2are calledadjacentife1 e26= , , the two edges are incident to the same vertex can visualize graphsG= (V,E) using pictures.

3 For each vertexv Vwe draw apoint (or small disc) in the plane. And for each edgeuv Ewe draw a continuouscurve starting and ending in the point/disc foruandv, examples of graphs and their corresponding pictures follow:V= [5],E={12,13,24}V={A,B,C,D,E},E={AB,AC,A D,AE,CE}Definition ( Graph variants). Adirected graphdirected graphis a pairG= (V,A) whereVis a finite set andA V2. Theedges of a directed Graph are also calledarcsarc. Amultigraphmultigraphis a pairG= (V,E) whereVis a finite set andEis a multiset ofelements from(V1) (V2), , we also allow loops and multiedges. Ahypergraphhypergraphis a pairH= (X,E) whereXis a finite set andE 2X\{ }. two graphsG1= (V1,E1) andG2= (V2,E2) we say thatG1andG2areisomorphicisomorphic,', denoted byG1'G2, if there exists a bijection :V1 V2withxy E1if and only if (x) (y) E2.

4 Loosely speaking,G1andG2are isomorphic ifthey are the same up to renaming of making structural comments, we do not normally distinguish between isomor-phic graphs. Hence, we usually writeG1=G2=instead ofG1'G2whenever vertices4are indistinguishable. Then we use the informal expressionunlabeled graphunlabeled Graph (or justgraphwhen it is clear from the context) to mean an isomorphism class of graphs and Graph all natural numbersnwe define: thecomplete graphcomplete Graph ,KnKnonnvertices as the (unlabeled) Graph isomorphic to([n],([n]2)). We also call complete graphscliques. forn 3, thecyclecycle,CnCnonnvertices as the (unlabeled) Graph isomorphic to([n],{{i,i+ 1}:i= 1,..,n 1} {n,1}). Thelength of a cycleis its numberof edges. We writeCn= The cycle of length 3 is also called atriangletriangle.

5 Thepathpath,PnPnonnvertices as the (unlabeled) Graph isomorphic to([n],{{i,i+ 1}:i= 1,..,n 1}). The vertices 1 andnare called theendpointsorendsof thepath. Thelength of a pathis its number of edges. We writePn= theempty graphempty Graph ,EnEnonnvertices as the (unlabeled) Graph isomorphic to([n], ).Empty graphs correspond to independent form 1, thecomplete bipartite graphcomplete bipartitegraph,Km,nKm,nonn+mvertices as the (unlabeled) Graph isomorphic to (A B,{xy:x A,y B}), where|A|=mand|B|=n,A B= . forr 2, acompleter-partitecompleter-partitegraph as an (unlabeled) Graph isomorphic to(A1 Ar,{xy:x Ai,y Aj,i6=j}),whereA1,..,Arare non-empty finite sets. In particular, the complete bipartitegraphKm,nis a complete 2-partite Graph . thePetersen graphPetersen graphas the (unlabeled) Graph isomorphic to(([5]2),{{S,T}:S,T ([5]2),S T= }).

6 For a natural numberk,k n, theKneser graphKneser Graph ,K(n,k)K(n,k) as the (unlabeled) Graph isomorphic to(([n]k),{{S,T}:S,T ([n]k),S T= }).Note thatK(5,2) is the Petersen then-dimensional hypercubehypercube,QnQnas the (unlabeled) Graph isomorphic to(2[n],{{S,T}:S,T 2[n],|S4T|= 1}).Vertices are labeled either by corresponding sets or binary indicators example the vertex{1,3,4}inQ6is coded by (1,0,1,1,0,0,0).Basic Graph parameters and degreesDefinition (V,E) be a Graph . We define the following parameters ofG. The graphGisnon-trivialnon-trivialif it contains at least one edge, ,E6= . Equiva-lently,Gis non-trivial ifGis not an empty Graph . Theorder ofGorder,|G|, denoted by|G|, is the number of vertices ofG, ,|G|=|V|. Thesize ofGsize, G , denoted by G , is the number of edges ofG, , G =|E|.

7 Note that if the order ofGisn, then the size ofGis between 0 and(n2). LetS Vbe a set of vertices. Theneighbourhood ofSneighbourhood,N(v), denoted byN(S), is theset of vertices inVthat have an adjacent vertex inS. The elements ofN(S) arecalledneighboursneighbourofS. Instead ofN({v}) forv Vwe usually writeN(v).7 If the vertices ofGare labeledv1,..,vn, then there is ann nmatrixAwithentries in{0,1}, which is called theadjacency matrixadjacency matrixand is defined as follows:vivj E A[i,j] = 1A= 0 1 1 01 0 1 11 1 0 00 1 0 0 A Graph and its adjacency matrix. Thedegreedegree,d(v)of a vertexvofG, denoted byd(v) or deg(v), is the number ofedges incident (v1) = 2, deg(v2) = 3, deg(v3) = 2, deg(v4) = 1 A vertex of degree 1 inGis called aleafleaf, and a vertex of degree 0 inGis calledanisolated vertexisolated vertex.

8 Thedegree sequencedegree sequenceofGis the multiset of degrees of vertices ofG, in theexample above the degree sequence is{1,2,2,3}. Theminimum degree ofGminimum degree, (G), denoted by (G), is the smallest vertex degree inG(it is 1 in the example). Themaximum degree ofGmaximum degree, (G), denoted by (G), is the highest vertex degree inG(it is 3 in the example). The graphGis calledk-regularregularfor a natural numberkif all vertices havedegreek. Graphs that are 3-regular are also calledcubiccubic. Theaverage degree ofGaverage degree,d(G)is defined asd(G) =( v Vdeg(v))/|V|. Clearly, wehave (G) d(G) (G) with equality if and only ifGisk-regular for 1(Handshake Lemma, ).For every graphG= (V,E) we have2|E|= v Vd(v). {(e,x) :e E(G),x V(G),x e}. Then|X|= v V(G)d(x)and|X|= e E(G)2 = 2|E(G)|.

9 The result sum of all vertex degrees is even and therefore the number ofvertices with odd degree is A graphH= (V ,E ) is asubgraph ofGsubgraph, , denoted byH G, ifV VandE E. IfHis a subgraph ofG, thenGis called asupergraph ofHsupergraph, , denotedbyG H. In particular,G1=G2if and only ifG1 G2andG1 G2. A subgraphHofGis called aninduced subgraphinduced subgraphofGif for every two verticesu,v V(H) we haveuv E(H) uv E(G). In the example aboveHis notan induced subgraph ofG. Every induced subgraph ofGcan be obtained bydeleting vertices (and all incident edges) :9 Every induced subgraph ofGis uniquely defined by its vertex set. We writeG[X]G[X]for the induced subgraph ofGon vertex setX, ,G[X] =(X,{xy:x,y X, xy E(G)}). ThenG[X] is called thesubgraph ofGinduced by thevertex setX V(G).

10 Example:GandG[{1,2,3,4}]: IfHandGare two graphs, then an(induced) copycopyofHinGis an (induced)subgraph ofGthat is isomorphic toH. A subgraphH= (V ,E ) ofG= (V,E) is called aspanning subgraphspanningsubgraphofGifV =V. A graphG= (V,E) is calledbipartitebipartiteif there exists natural numbersm,nsuchthatGis isomorphic to a subgraph ofKm,n. In this case, the vertex set can bewritten asV=A Bsuch thatE {ab|a A,b B}. The setsAandBarecalledpartite sets ofGpartite sets. Acycle (path, clique)cliqueinGis a subgraphHofGthat is a cycle (path, completegraph). Anindependent setindependent setinGis an induced subgraphHofGthat is an empty Graph . Awalkwalk(of lengthk) is a non-empty alternating sequencev0e0v1e1 ek 1vkofvertices and edges inGsuch thatei={vi,vi+1}for alli < k. Ifv0=vk, thewalk isclosedclosed walk.