Lecture Notes on GRAPH THEORY

1 Lecture Notes onGRAPH THEORYTero HarjuDepartment of MathematicsUniversity of TurkuFIN-20014 Turku, Finlande-mail: 2011 Contents1 introduction .. Graphs and their plane figures .. Subgraphs .. Paths and cycles .. 112 Connectivity of Graphs.. Bipartite graphs and trees .. Connectivity .. 233 Tours and Matchings.. Eulerian graphs .. Hamiltonian graphs .. Matchings .. 354 Colourings.. Edge colourings .. Ramsey THEORY .. Vertex colourings .. 535 Graphs on Surfaces.. Planar graphs .. Colouring planar graphs .. Genus of a GRAPH .. 766 Directed Graphs.. Digraphs.. Network Flows .. 90 Index.. 971 IntroductionGraph THEORY may be said to have its begin-ning in 1736 when EULER considered the (gen-eral case of the)K nigsberg bridge problem:Does there exist a walk crossing each of theseven bridges of K nigsberg exactly once? (So-lutio Problematis ad geometriam situs perti-nentis,Commentarii Academiae Scientiarum Impe-rialis Petropolitanae8 (1736), pp.)

2 128-140.)It took 200 years before the first book on GRAPH THEORY was written. This was The-orie der endlichen und unendlichen Graphen ( Teubner, Leipzig, 1936) by K NIGin1936. Since then GRAPH THEORY has developed into an extensive and popular branch ofmathematics, which has been applied to many problems in mathematics, computerscience, and other scientific and not-so-scientific areas. Forthe history of early graphtheory, BIGGS, LLOYD WILSON, GRAPH THEORY 1736 1936 , ClarendonPress, are no standard notations for GRAPH theoretical objects. This is natural, be-cause the names one uses for the objects reflect the applications. Thus, for instance, ifwe consider a communications network (say, for email) as a GRAPH , then the comput-ers taking part in this network, are called nodes rather thanvertices or points. On theother hand, other names are used for molecular structures inchemistry, flow chartsin programming, human relations in social sciences, and so lectures studyfinite graphsand majority of the topics is included BONDY, MURTY, GRAPH THEORY with Applications , Macmillan, DIESTEL, GRAPH THEORY , Springer-Verlag, HARARY, GRAPH THEORY , Addison-Wesley, WEST, introduction to GRAPH THEORY , Prentice Hall, WILSON, introduction to GRAPH THEORY , Longman, (3rd ed.

3 These lectures we studycombinatorial aspectsof graphs. For morealgebraictopicsand methods, seeN. BIGGS, Algebraic GRAPH THEORY , Cambridge University Press, (2nd ed.) GODSIL, ROYLE, Algebraic GRAPH THEORY , Springer, forcomputational aspects, seeS. EVEN, GRAPH Algorithms , Computer Science Press, these Lecture Notes we mention several open problems thathave gained respectamong the researchers. Indeed, GRAPH THEORY has the advantage that it contains easilyformulated open problems that can be stated early in the THEORY . Finding a solutionto any one of these problems is another with a star ( ) in their heading are and notions For a finite setX,|X|denotes its size (cardinality, the number of its elements). Let[1,n] ={1, 2, .. ,n},and in general,[i,n] ={i,i+1, .. ,n}for integersi n. For a real numberx, thefloorand theceilingofxare the integers x =max{k Z|k x}and x =min{k Z|x k}. A family{X1,X2.}

4 ,Xk}of subsetsXi Xof a setXis apartitionofX, ifX=[i [1,k]XiandXi Xj= for all differentiandj. For two setsXandY,X Y={(x,y)|x X,y Y}is theirCartesian product, andX Y= (X\Y) (Y\X)is theirsymmetric difference. HereX\Y={x|x X,x/ Y}. Two integersn,k N(oftenn=|X|andk=|Y|for setsXandY) have thesameparity, if both are even, or both are odd, that is, ifn k(mod 2). Otherwise, theyhave opposite THEORY has abundant examples ofNP-complete problems. Intuitively, aproblem is in P1if there is an efficient (practical) algorithm to find a solutionto it. Onthe other hand, a problem is in NP2, if it is first efficient to guess a solution and thenefficient to check that this solution is correct. It is conjectured (and not known) thatP6=NP. This is one of the great problems in modern mathematics and theoreticalcomputer science. If the guessing in NP-problems can be replaced by an efficientsystematic search for a solution, then P=NP.]

5 For any one NP-complete problem, if itis in P, then necessarily P= by an algorithm in polynomially many steps on thesize of the problem polynomially many steps on the size of the problem Graphs and their plane Graphs and their plane figuresLetVbe afiniteset, and denote byE(V) ={{u,v} |u,v V,u6=v}.the2-setsofV, , subsets of two distinct A pairG= (V,E)withE E(V)is called agraph(onV). The elementsofVare theverticesofG, and those ofEtheedgesofG. The vertex set of a graphGis denoted byVGand its edge set byEG. ThereforeG= (VG,EG).In literature, graphs are also calledsimple graphs; vertices are callednodesorpoints;edges are calledlinesorlinks. The list of alternatives is long (but still finite).A pair{u,v}is usually written simply asuv. Notice that thenuv=vu. In order tosimplify notations, we also writev Gande Ginstead ofv VGande For a graphG, we denote G=|VG|and G=|EG|.The number Gof the vertices is called theorderofG, and Gis thesizeofG.

6 For anedgee=uv G, the verticesuandvare itsends. Verticesuandvareadjacentorneighbours, ifuv G. Two edgese1=uvande2=uwhaving a common end, areadjacentwith each graphGcan be represented as a plane figure bydrawing a line (or a curve) between the pointsuandv(representing vertices) ife=uvis an edge figure on the right is a geometric representationof the graphGwithVG={v1,v2,v3,v4,v5,v6}andEG={v 1v2,v1v3,v2v3,v2v4,v5v6}.v1v2v3v4v5v6 Often we shall omit the identities (namesv) of the vertices in our figures, in whichcase the vertices are drawn as anonymous can be generalized by allowingloopsvvandparallel(ormultiple)ed gesbetween vertices to obtain amultigraphG= (V,E, ), whereE={e1,e2, .. ,em}isa set (of symbols), and :E E(V) {vv|v V}is a function that attaches anunordered pair of vertices to eache E: (e) = that we can have (e1) = (e2). This is drawn inthe figure ofGby placing two (parallel) edges that con-nect the common ends.

7 On the right there is (a draw-ing of) a multigraphGwith verticesV={a,b,c}and edges (e1) =aa, (e2) =ab, (e3) =bc, and (e4) = Graphs and their plane figures5 Later we concentrate on (simple) We also studydirected graphsordigraphsD= (V,E), where the edges have a direction, that is, theedges are ordered:E V V. In this case,uv6= directed graphs have representations, where the edges are drawn as digraph can contain edgesuvandvuofopposite and digraphs can also be coloured, labelled, and weighted:DEFINITION. A function :VG Kis avertex colouringofGby a setKof function :EG Kis anedge colouringofG. Usually,K= [1,k]for somek R(oftenK N), then is aweight functionor adistance of graphsDEFINITION. Two graphsGandHareisomorphic, denoted byG =H, if there existsa bijection :VG VHsuch thatuv EG (u) (v) EHfor allu,v isomorphic if the vertices ofHare renamings of those isomorphic graphs enjoy the same GRAPH theoretical properties, andthey are oftenidentified.

8 In particular, all isomorphic graphs have the same plane figures (exceptingthe identities of the vertices). This shows in the figures, where we tend to replace thevertices by small circles, and talk of the GRAPH although there are, in fact, infinitelymany such following graphs areisomorphic. Indeed, the required iso-morphism is given byv17 1,v27 3,v37 4,v47 2,v57 there exist an efficient algorithm to check whether any twogiven graphs are isomorphic or not?The following table lists the number 2(n2)of all graphs on a given set ofnvertices,and the number of all nonisomorphic graphs onnvertices. It tells that at least forcomputational purposes an efficient algorithm for checking whether two graphs areisomorphic or not would be greatly 7682 097 152268 435 456236>6 1010nonisomorphic1241134156104412 346274 Graphs and their plane figures6 Other representationsPlane figures catch graphs for our eyes, but if a problem on graphs is to bepro-grammed, then these figures are, to say the least, unsuitable.

9 Integermatrices are idealfor computers, since every respectable programming language has array structuresfor these, and computers are good in crunching {v1, .. ,vn}be ordered. Theadjacency ma-trixofGis then n-matrixMwith entriesMij=1orMij=0 according to whethervivj Gorvivj/ instance, the GRAPH in Example has an adja-cency matrix on the right. Notice that the adjacencymatrix is always symmetric (with respect to its diag-onal consisting of zeros). 0 1 1 0 11 0 0 1 11 0 0 1 00 1 1 0 01 1 0 0 0 A GRAPH has usually many different adjacency matrices, one for each ordering ofits setVGof vertices. The following result is obvious from the graphs G and H are isomorphic if and only if they have a common adja-cency matrix. Moreover, two isomorphic graphs have exactly thesame set of adjacency can also be represented by sets. For this, letX={X1,X2, .. ,Xn}be afamily of subsets of a setX, and define theintersection graphGXas the GRAPH withverticesX1.

10 ,Xn, and edgesXiXjfor alliandj(i6=j) withXi Xj6= .Theorem GRAPH is an intersection GRAPH of some family of a GRAPH , and define, for allv G, a setXv={{v,u} |vu G}.ThenXu Xv6= if and only ifuv G. Lets(G)be the smallest size of a base setXsuch thatGcan be represented as anintersection GRAPH of a family of subsets ofX, that is,s(G) =min{|X| |G =GXfor someX 2X}.How small cans(G)be compared to the order G(or the size G) of the GRAPH ? It wasshown by KOU, STOCKMEYER ANDWONG(1976) that it is algorithmically difficult todetermine the numbers(G) the problem is yet another example, letA Nbe a finite set of natural numbers,and letGA= (A,E)be the GRAPH withrs Eif and only ifrands(forr6=s) have acommon divisor>1. As an exercise, we state:All graphs can be represented in the formGAfor some set A of natural SubgraphsIdeally, given a nice problem the local properties of a graphdetermine a these situations we deal with (small) parts of the GRAPH (subgraphs), and a solu-tion can be found to the problem by combining the informationdetermined by theparts.