1.1 Graphses r, y ofG are adjacent, or neighbours, if (r,y) is an edgeadjacentof G. Two edges e + f are adjacent if they have an end in common. If allneighbourthe vertices of G are pairwise adjacent, then G is complete. A completecompleteKngraph on n vertices is a Kn; a K3 is called a triangle. are called independent.Pairwise non-adiacent vertices or edgespelaneMore formally, a seor of edges is indenendent if notwoof itstoforticoselenadjacent.IndependentsetsofverticesarealsocalledstableLet G= (V,E) and G'- (V', E') be two graphs. A map p:V-V"mophnisahommorphism from G to G' ifit preserves the adjacency of vertices,that is, if (o(r), p(y)) E' whenever (r,y) e E. Then, in particularfor every vertex r' in the image of its inverse image p-'(r') is anindependent set of vertices in G.If ois biiective and its inverse11also a homomorphism (so that ry e E p(r)p(y) e E' for all , y e V),rphism,saythatG and G'are isomorphic.writeisomorphicG - G'. An isomorphism from G to itself is an automorphism of G.2We do not normally distinguish between isomorphic graphs.Thus,we usually write G = G' rather than G ~ G', speak of the completegraph on 17 vertices, and so on. If we wish to emphasize that we areonly interested in the isomorphism type of a given graph, we informallyrefer to it aanabstractgraphA class of graphs that is closed under isoorphiscalled a graphproperty.For example, containing a triangle'is a graph property: ifpropertyG contains three pairwise adjacent vertices then so does every graphisomorphic to G. A map taking graphs as arguments is called a graphinvariant if it assigns equal values to isomorphic graphs. The numberinvariantof vertices and the number of edges of a graph are two simple graphinvariants: the greatest number of pairwise adiacent vertices is anotherWe set GUG' := (VUV',EUE') and GnG' := (VnV', EnE').GUQIf GnG'=0,then G and G' are disjont.IfVCVand E'E,thenGnG'2GL1..42GnG'GUGG-GFig.2. Union,diference and intersection the vertices23induce (or span) a triangle in GUG' but not in G
1.1 Graphs 3 Two vertices x, y of G are adjacent, or neighbours, if {x, y} is an edge adjacent of G. Two edges e = f are adjacent if they have an end in common. If all neighbour the vertices of G are pairwise adjacent, then G is complete. A complete complete graph on n vertices is a Kn; a K3 is called a triangle. Kn Pairwise non-adjacent vertices or edges are called independent. More formally, a set of vertices or of edges is independent if no two of its independent elements are adjacent. Independent sets of vertices are also called stable. Let G = (V,E) and G = (V , E ) be two graphs. A map ϕ: V →V is a homomorphism from G to G if it preserves the adjacency of vertices, homomorphism that is, if {ϕ(x), ϕ(y)} ∈ E whenever {x, y} ∈ E. Then, in particular, for every vertex x in the image of ϕ its inverse image ϕ−1(x ) is an independent set of vertices in G. If ϕ is bijective and its inverse ϕ−1 is also a homomorphism (so that xy ∈ E ⇔ ϕ(x)ϕ(y) ∈ E for all x, y ∈ V ), we call ϕ an isomorphism, say that G and G are isomorphic, and write isomorphic G G . An isomorphism from G to itself is an automorphism of G. We do not normally distinguish between isomorphic graphs. Thus, we usually write G = G rather than G G , speak of the complete = graph on 17 vertices, and so on. If we wish to emphasize that we are only interested in the isomorphism type of a given graph, we informally refer to it as an abstract graph. A class of graphs that is closed under isomorphism is called a graph property. For example, ‘containing a triangle’ is a graph property: if property G contains three pairwise adjacent vertices then so does every graph isomorphic to G. A map taking graphs as arguments is called a graph invariant if it assigns equal values to isomorphic graphs. The number invariant of vertices and the number of edges of a graph are two simple graph invariants; the greatest number of pairwise adjacent vertices is another. We set G ∪ G := (V ∪ V , E ∪ E ) and G ∩ G := (V ∩V , E ∩ E ). G ∪ G If G ∩ G = ∅, then G and G are disjoint. If V ⊆ V and E ⊆ E, then G ∩ G G ∪ − G G ∩ 1 2 3 4 5 G 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 G G G G Fig. 1.1.2. Union, difference and intersection; the vertices 2,3,4 induce (or span) a triangle in G ∪ G but not in G
1. The Basics4G' is a subgraph of G (and G a supergraph of G'), written as G' C GsubgraphLess formally, we say that G contains G'. If G' C G and G' + G, thenG'CGG' is a proper subgraph of G.区口口Fig. 1.1.3. A graph G with subgraphs G' and G":G' is an induced subgraph of G, but G" is notIf G' C G and G' contains all the edges ry e E with ,y e V', theninducedG' is an induced subgraph of G; we say that V' induces or spans G' in Gsubgraphand write G' =: G[V']. Thus if U C V is any set of vertices, then G[U]G]denotes the graphU whose edges are precisely the edges of G withboth ends in U. If H is aa subgraph of G,not necesessarilyinduced.weabbreviate G[V(H)] to G[H], Finally, G' C G is a spanning subgraphspanningof G if Vi spans all of G, i.e. if VI = V.If U is any set of vertices (usually of G), we write G-U forG[V U]. In other words, G- U is obtained from G by deleting allthe vertices in UnV and their incident edges. If U = (u) is a singleton,wewriteGu rather than G - [u). Instead of G - V(G') we simplywriteG-GFoAsubsetFof[V2wewriteG-F:=(V.EF)and+G+F := (V, EUF); as above, G- (e]) and G+[e) are abbreviated toedleimalG- and G+e. We call G edge-mazimal with a given graph propertyif G itself has the property but no graph (V,F) with F2 E doesminimalMoregenerally,wlhenwecallagraphminimalormarimalwithsomeproperty but have not specified any particular ordering, we are referringmaximalto the subgraph relation.When we speak of minimal or maximal sets ofvertices es, the reference is simply to set inclusionIf G and G' are disjoinnt, we denote by G*G' the graph obtainG*G'from GUG' by joining all the vertices of G to all the vertices of G'. Folcompleexample, K?+ K3 - K. The complement C of G is the graph on Vment Gwith edge set [V]? E. The line graph L(G) of G is the graph on E inLegmaphwhich ,y e E are adjacent as vertices if and only if they are adjacentas edges inGFig. 1.1.4. A graph isomorphic to its complement
4 1. The Basics G is a subgraph of G (and G a supergraph of G subgraph ), written as G ⊆ G. Less formally, we say that G contains G . If G ⊆ G and G G = G, then ⊆ G G is a proper subgraph of G. G G G Fig. 1.1.3. A graph G with subgraphs G and G: G is an induced subgraph of G, but G is not If G ⊆ G and G contains all the edges xy ∈ E with x, y ∈ V , then G is an induced subgraph of G; we say that V induces or spans G in G, induced subgraph and write G =: G[V ]. Thus if U ⊆ V is any set of vertices, then G[U] G[U] denotes the graph on U whose edges are precisely the edges of G with both ends in U. If H is a subgraph of G, not necessarily induced, we spanning abbreviate G[V (H)] to G[H]. Finally, G ⊆ G is a spanning subgraph of G if V spans all of G, i.e. if V = V . − If U is any set of vertices (usually of G), we write G − U for G[V U]. In other words, G − U is obtained from G by deleting all the vertices in U ∩V and their incident edges. If U = {v} is a singleton, we write G − v rather than G − {v}. Instead of G − V (G ) we simply write G − G . For a subset F of [V ] 2 + we write G − F := (V, E F) and G + F := (V, E ∪F); as above, G − {e} and G + {e} are abbreviated to G − e and G + e. We call G edge-maximal with a given graph property edgemaximal if G itself has the property but no graph (V,F) with F E does. minimal More generally, when we call a graph minimal or maximal with some maximal property but have not specified any particular ordering, we are referring to the subgraph relation. When we speak of minimal or maximal sets of vertices or edges, the reference is simply to set inclusion. If G and G are disjoint, we denote by G ∗ G G ∗ G the graph obtained from G∪G by joining all the vertices of G to all the vertices of G . For example, K2 ∗ K3 = K5. The complement G of G is the graph on V complement G with edge set [V ] 2 E. The line graph L(G) of G is the graph on E in which x, y ∈ E are adjacent as vertices if and only if they are adjacent line graph L(G) as edges in G. G G Fig. 1.1.4. A graph isomorphic to its complement
1.2. The degree of a vertex51.2 The degree of a vertexLet G = (V, E) be a (non-empty) graph. The set of neighbours of avertex u in G is denoted by Nc(u), or briefly by N().' More generallyN(u)for U V, the neighbours in VU of vertices in U are called neighboursof U; their set is denoted by N(U),egree (or valency) dc(u) =- d(u) of a vertex u is the numberdegree d(u)[E(u)[ of edgeesatw:byourdefiron of a graph,? this is equal to thember ofneighboursofu.Avertex ofdegreeOis isolated.Thenumberisolateds(G) := min ( d(v) [ w e V) is the minimum degree of G, the number8(G)A(G) := max ( d(u) I u e V) its marimum degree. If all the vertices(G)of G have the same degree k, then G is k-regular, or simply regular. Aregularcubic3-regular graph is called cubic.The numberd(G)=mEd(u)Vd(G)is the average degree of G. Clearly,8(G) ≤d(G)≤△(G)The average degree quantifies globally what is measured locally by thevertex degrees: the number of edges of G per vertex. Somesitwillbe convenient to express this ratio directly, as e(G) := [El/IV].e(G)The quantities d and e are, of course, intimately related. Indeed,if we sum up all the vertex degrees in G, we count every edge exactlytwice: once from each of its ends. Thus[E] = d(0) = d(G) [V],and therefore(G) = d(G)Proposition 1.2.1. The num[10.3.1]of vertices of odd degree inagraph isalwavseven口Proof. As [E] - Zvev d(u) is an integer, Zvev d(u) is even.LHerelsewhere, we drop the index referring to the underlying graph if threference is clear.2 but not for multigraphs: see Section 1.10
1.2. The degree of a vertex 5 1.2 The degree of a vertex Let G = (V,E) be a (non-empty) graph. The set of neighbours of a vertex v in G is denoted by NG(v), or briefly by N(v).1 More generally N(v) for U ⊆ V , the neighbours in V U of vertices in U are called neighbours of U; their set is denoted by N(U). The degree (or valency) dG(v) = d(v) of a vertex v is the number degree d(v) |E(v)| of edges at v; by our definition of a graph,2 this is equal to the number of neighbours of v. A vertex of degree 0 is isolated. The number isolated δ(G) := min { d(v) | v ∈ V } is the minimum degree of G, the number δ(G) Δ(G) := max { d(v) | v ∈ V } its maximum degree. If all the vertices Δ(G) of G have the same degree k, then G is k-regular, or simply regular. A regular 3-regular graph is called cubic. cubic The number d(G) := 1 |V | v∈V d(v) d(G) is the average degree of G. Clearly, average degree δ(G) d(G) Δ(G). The average degree quantifies globally what is measured locally by the vertex degrees: the number of edges of G per vertex. Sometimes it will be convenient to express this ratio directly, as ε(G) := |E|/|V |. ε(G) The quantities d and ε are, of course, intimately related. Indeed, if we sum up all the vertex degrees in G, we count every edge exactly twice: once from each of its ends. Thus |E| = 1 2 v∈V d(v) = 1 2 d(G)· |V | , and therefore ε(G) = 1 2 d(G). Proposition 1.2.1. The number of vertices of odd degree in a graph is [10.3.1] always even. Proof. As |E| = 1 2 v∈V d(v) is an integer, v∈V d(v) is even. 1 Here, as elsewhere, we drop the index referring to the underlying graph if the reference is clear. 2 but not for multigraphs; see Section 1.10
61. The BasicIfa graph has largeminimum degree.i.e.evervwhere.locally.manvedges per vertex, it also has many edges per vertex globally: e(G) d(G) ≥ o(G). Conversely, of course, its average degree may be largeeven when its miinimumdegreeissmall.However,theverticesoflargedegree cannot be scattered completely among vertices of small degree: asthe next proposition shows, every graph G has a subgraph whose avelragedegree is no less than the average degree of G, and whose minimundegree is more than half its average degree1.2Pro122FhGwithatlehas a subioroneedgegraph H with (H)>e(H)≥e(G)Proof. To construct H from G, let us try to delete vertices of smalldegree one by one, until only vertices of large degree remain. Up towhich degree d(v) can we afford to delete a vertex v, without lowering e?Clearly, up to d(u) = e: then the number of vertices decreases by 1and the number of edges by at most e, so the overall ratio e of edges tovertices will not decreasFormally, we construct a sequence G = Go 2 Gi 2 ... of inducedsubgraphs of G as follows. If G, has a vertex v; of degree d(v:) ≤ e(G)reletGiG,-v:if notweterminate ouH := G, By the choices of u; we have e(Gi+1) ≥ e(G) for all i, andhence e(H) ≥ e(G).What else can we say about the graph H? Since e(K') = 0 < e(G)none of the graphs in our sequenceistrivial,soinparticularH+.Thefact that H has no vertex suitable for deletion thus implies (H) > e(H)as claimed.1.3 Paths and cyclesA path is a non-empty graph P.= (V,E) of the formpathV= [1o, T1,...,]E = [ror1,ri2,*,k-1k],where the r, are all distinct. The vertices To and rk are linked by P andare called its endvertices or ends; the vertices Ti,.., k-1 are the innervertices of P.The numberofedges of a path is its length, and the pathlengthpkof length k is denoted by Pk. Note that k is allowed to be zero; thus,00一KWe often refer to a path by the natural sequence of its vertices,3MorepiselybyeofthwonaturalsqunkandVdenotetnhelpstofixitoproperty, ete
6 1. The Basics If a graph has large minimum degree, i.e. everywhere, locally, many edges per vertex, it also has many edges per vertex globally: ε(G) = 1 2 d(G) 1 2 δ(G). Conversely, of course, its average degree may be large even when its minimum degree is small. However, the vertices of large degree cannot be scattered completely among vertices of small degree: as the next proposition shows, every graph G has a subgraph whose average degree is no less than the average degree of G, and whose minimum degree is more than half its average degree: Proposition 1.2.2. Every graph G with at least one edge has a sub- [1.4.3] [7.2.2] graph H with δ(H) > ε(H) ε(G). Proof. To construct H from G, let us try to delete vertices of small degree one by one, until only vertices of large degree remain. Up to which degree d(v) can we afford to delete a vertex v, without lowering ε? Clearly, up to d(v) = ε : then the number of vertices decreases by 1 and the number of edges by at most ε, so the overall ratio ε of edges to vertices will not decrease. Formally, we construct a sequence G = G0 ⊇ G1 ⊇ ... of induced subgraphs of G as follows. If Gi has a vertex vi of degree d(vi) ε(Gi), we let Gi+1 := Gi − vi; if not, we terminate our sequence and set H := Gi. By the choices of vi we have ε(Gi+1) ε(Gi) for all i, and hence ε(H) ε(G). What else can we say about the graph H? Since ε(K1)=0 < ε(G), none of the graphs in our sequence is trivial, so in particular H = ∅. The fact that H has no vertex suitable for deletion thus implies δ(H) > ε(H), as claimed. 1.3 Paths and cycles path A path is a non-empty graph P = (V,E) of the form V = {x0, x1,...,xk} E = {x0x1, x1x2,...,xk−1xk} , where the xi are all distinct. The vertices x0 and xk are linked by P and are called its endvertices or ends; the vertices x1,...,xk−1 are the inner length vertices of P. The number of edges of a path is its length, and the path of length k is denoted by Pk P . Note that k is allowed to be zero; thus, k P0 = K1. We often refer to a path by the natural sequence of its vertices,3 3 More precisely, by one of the two natural sequences: x0 ...xk and xk ...x0 denote the same path. Still, it often helps to fix one of these two orderings of V (P) notationally: we may then speak of things like the ‘first’ vertex on P with a certain property, etc.
1.3Paths and cycleFig. 1.3.1. A path P = pe in Giting, say, P = rozi -.. h and calling P a path from ro to rx (as wellras between to and k)For 0≤i≤j<k we writeaPy,PPa,= To...a,P:=....kE,PajTi.TandDPi, = .-2,P:=Li+...Iki,Pi=Ti+1-.T-1for the appropriate subpaths of P. We use similar intuitive notation forthe concatenation of paths; for example, if the union PrUrQyUyR ofthree paths is again a path, we may simply denote it by PrQyR.PaQyRFig. 1.3.2. Paths P, Q and rPyQzGiven sets A, B of vertices, we call P =Co..rkanA-BpathifA-BpathV(P)nA= (zo) and V(P)nB - (rk), As before, we write a-B pathpeadtrather than (aj-B path, etc.Two or more paths are independent ifnone of them contains an inner vertex of another. Two a-b paths, forinstance, are independent if and only if a and b are their only commonverticesGiven a graph H, we call P an H-path if P is non-trivial and meetsH-pathHexactlynitsendsInparticular,theedgeofanyH-pathoflengthis never an edge of H
1.3 Paths and cycles 7 G P Fig. 1.3.1. A path P = P6 in G writing, say, P = x0x1 ...xk and calling P a path from x0 to xk (as well as between x0 and xk). For 0 i j k we write xP y, P ˚ P xi := x0 ...xi xiP := xi ...xk xiP xj := xi ...xj and P ˚ := x1 ...xk−1 P˚xi := x0 ...xi−1 ˚xiP := xi+1 ...xk ˚xiP˚xj := xi+1 ...xj−1 for the appropriate subpaths of P. We use similar intuitive notation for the concatenation of paths; for example, if the union P x ∪ xQy ∪ yR of three paths is again a path, we may simply denote it by P xQyR. P xQyR x xP yQz y z x P y Q z Fig. 1.3.2. Paths P, Q and xP yQz Given sets A, B of vertices, we call P = x0 ...xk an A–B path if A–B path V (P) ∩ A = {x0} and V (P) ∩ B = {xk}. As before, we write a–B path rather than {a}–B path, etc. Two or more paths are independent if independent none of them contains an inner vertex of another. Two a–b paths, for instance, are independent if and only if a and b are their only common vertices. Given a graph H, we call P an H- path if P is non-trivial and meets H- path H exactly in its ends. In particular, the edge of any H-path of length 1 is never an edge of H.