Graph Theory - KIT

1 Graph TheoryLecture by Prof. Dr. Maria AxenovichLecture notes by M onika Csik os, Daniel Hoske and Torsten Ueckerdt1 Contents1 Introduction32 Notations33 Preliminaries44 Matchings135 Connectivity176 Planar graphs227 Colorings278 Extremal Graph theory309 Ramsey theory3410 Flows3811 Random graphs4012 Hamiltonian cycles4213 Kuratowski s Theorem .. Other coloring results .. Preparation for Tur an s theorem .. Induced Ramsey numbers .. Flows .. Group-valued flows .. Random graphs .. 105 References108 Index10921 IntroductionThese notes include major definitions and theorems of the Graph Theory lecture heldby Prof.

2 Maria Axenovich at KIT in the winter term 2017/18. Most of the contentis based on the book Graph Theory by Reinhard Diestel [4]. A free version of thebook is available The first part includes onlyformulations and definitions. The second part includes the : G= (V,E) is an arbitrary (undirected, simple) Graph n:=|V|is its number of vertices m:=|E|is its number of edges2 Notationsnotationdefinitionmeaning(Vk),V finite 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,..,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 ofAandB33 PreliminariesDefinition ,GgraphGis an ordered pair (V,E), whereVis a finite set andE (V2)is a set of pairs of elements inV.

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

4 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. Loosely speaking,G1andG2are isomorphic ifthey are the same up to renaming of making structural comments, we do not normally distinguish between isomor-phic graphs.

5 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)). Complete graphs correspond tocliques. 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. thepathpath,PnPnonnvertices as the (unlabeled) Graph isomorphic to([n],{{i,i+ 1}:i= 1.)}

6 ,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 sets. 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= .5 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= }).

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

8 Thesize ofGsize, G , denoted by G , is the number of edges ofG, , G =|E|.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). 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] = 17A= 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.

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

10 For every graphG= (V,E) we have2|E|= v Vd(v).Corollary 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) : Every induced subgraph ofGis uniquely defined by its vertex set.