xviContents1l. Random Graphs29311.1 The notion of a random graph29411.2 The probabilistic method*29911.3 Properties of almost all graphs*30211.4 Threshold functions and :....306na312ExerciseNotes31312. Minors, Trees and WQO31512.1 Well-quasi-ordering*...31612.2Thegraph31712.3 Tree-decompositio31932712.4Tree-widthandforbiddenminor12.5 The graph minor theorem(*)....341350ExercisesNotes354A. Infinite sets357B. Surfaces.361Hints for all the exerci..369Index393Sym409
xvi Contents 11. Random Graphs ............................................... 293 11.1 The notion of a random graph* ................................. 294 11.2 The probabilistic method* ...................................... 299 11.3 Properties of almost all graphs* ................................ 302 11.4 Threshold functions and second moments ....................... 306 Exercises ....................................................... 312 Notes .......................................................... 313 12. Minors, Trees and WQO ..................................... 315 12.1 Well-quasi-ordering* ............................................ 316 12.2 The graph minor theorem for trees* ............................ 317 12.3 Tree-decompositions ............................................ 319 12.4 Tree-width and forbidden minors ............................... 327 12.5 The graph minor theorem(∗) .................................... 341 Exercises ....................................................... 350 Notes .......................................................... 354 A. Infinite sets ..................................................... 357 B. Surfaces ......................................................... 361 Hints for all the exercises............................................... 369 Index .................................................................. 393 Symbol index .......................................................... 409
1The BasicsThis chapter gives a gentle yet concise introduction to most of the ter-minology used later in the book. Fortunately, much of standard graphtheoretic terminology is so intuitive that it is easy to remember; the fewterms better understood in their proper setting will be introduced later,when their time has comeSection 1.1 offers a brief but self-contained summary of the mostbasic definitions in graph theory, those centred round the notion of agraph. Most readers will have met these definitions before, or will havethem explained to them as they begin to read this book. For this reason,Section 1.1 does not dwell on these definitions more than clarity requires:its main purpose is to collect the most basic terms in one place, for easyreference later.From Section 1.2 onwards, all new definitions wil be brought to lifealmost immediately by a number of simple yet fundamental propositions.Often, these will relate the newly defined terms to one another: thequestion of how the value of one invariant influences that of anotherunderlies much of graph theory, and it will be good to become familiarwith this line of thinking early.By N we denote the set of natural numbers, including zero. The setZ/nZ of integers modulo n is denoted by Zn; its elements are writtenZnasi:=i+nZHorreal number we denote by [] the greatestinteger < a, and by [z] the least integer ≥ a. Logarithms written as[a] [] log'are taken at base 2; the natural logarithm will be denoted by In'log, InA set A = (A1,.., Ak] of disjoint subsets of a set A is a partitionpartitionof A if the union UA of all the sets A; e A is A and A; + O for every i.UAAnother partition (Ai...,.A'J of A refines the partition Aif each A is[A]kcontained in some Aj. By [A]* we denote the set of all k-element subsetsof A. Sets with k elements will be called k-sets; subsets with k elementsare k-subsets.k-set
1 The Basics This chapter gives a gentle yet concise introduction to most of the terminology used later in the book. Fortunately, much of standard graph theoretic terminology is so intuitive that it is easy to remember; the few terms better understood in their proper setting will be introduced later, when their time has come. Section 1.1 offers a brief but self-contained summary of the most basic definitions in graph theory, those centred round the notion of a graph. Most readers will have met these definitions before, or will have them explained to them as they begin to read this book. For this reason, Section 1.1 does not dwell on these definitions more than clarity requires: its main purpose is to collect the most basic terms in one place, for easy reference later. From Section 1.2 onwards, all new definitions will be brought to life almost immediately by a number of simple yet fundamental propositions. Often, these will relate the newly defined terms to one another: the question of how the value of one invariant influences that of another underlies much of graph theory, and it will be good to become familiar with this line of thinking early. By N we denote the set of natural numbers, including zero. The set Z/nZ of integers modulo n is denoted by Zn; its elements are written Zn as i := i + nZ. For a real number x we denote by x the greatest integer x, and by x the least integer x. Logarithms written as x, x ‘log’ are taken at base 2; the natural logarithm will be denoted by ‘ln’. log, ln A set A = { A1,...,Ak } of disjoint subsets of a set A is a partition partition of A if the union A of all the sets Ai ∈ A is A and Ai = ∅ for every i. A Another partition { A 1,...,A } of A refines the partition A if each A i is contained in some Aj . By [A] k we denote the set of all k-element subsets [A] k of A. Sets with k elements will be called k-sets; subsets with k elements are k-subsets. k-set
21.The Basics1.1 GraphsA graph is a pair G -(V,E) of sets such that E C[V]’; thus, the elementsgraphof E are 2-element subsets of V. To avoid notational ambiguities, weshall always assume tacitly that VnE = 0. The elements of V are thevertices (or nodes, or points) of the graph G, the elements of E are itsvertexedgeedges (or lines).The usual way to picture a graph is by drawing a dot foreach vertex and joining two of these dots by a line if the correspondingtwo vertices form an edge. Just how these dots and lines are drawn isconsidered irrelevant: all that matters is the information of which pairsof vertices form an edge and which do not.AFig. 1.1.1. The graph on V - (1,...,7) with edge setE = ((1,2), (1,5]. (2,5], (3,4], (5, 7)A graph with vertex set V is said to be a graph on V. The vertexonV(G),E(G) set of a graph G is referred to as V(G), its edge set as E(G). Theseconventions are independent of any actual names of these two sets: thevertex set W of a graph H = (W, F) is still referred to as V(H), not asW(H). We shall not always distinguish strictly between a graph and itsvertex or edge set. For example, we may speak of a vertex ue G (ratherthan u e V(G), an edge e e G, and so on.The number of vertices of a graph G is its order, written as JGl; itsordernumber of edges is denoted by Gl.Graphs are finite, infinite, countable[G], IGand so on according to their order. Except in Chapter 8, our graphs willbe finite unless otherwise stated.erivialFor the empty graph (0, 0)we simply write 0. Agraph of order 0 or1is called trivial. Sometimes, e.g. to start an induction, trivial graphs cangraphbe useful; at other times they form silly counterexamples and become anuisance. To avoid cluttering the text with non-triviality conditions, weshall mostly treat the trivial graphs, and particularly the empty graph Owith generous disregard.incidentA vertex v is incident with an edge e if v e e; then e is an edge at y.The two vertices incident with an edge are its endvertices or ends, andendsan edge joins its ends. An edge (r,y) is usually written as ry (or yr).If e X and y e Y, then ry is an X-Y edge. The set of all X-Y edgesE(X,Y)in a set E is denoted by E(X,Y); instead of E({r),Y) and E(X, (y)we simply write E(r,Y) and E(X,y). The set of all the edges in E at aE(u)vertex is denoted by E(u)
2 1. The Basics 1.1 Graphs A graph is a pair G = (V,E) of sets such that E ⊆ [V ] 2 graph ; thus, the elements of E are 2-element subsets of V . To avoid notational ambiguities, we shall always assume tacitly that V ∩ E = ∅. The elements of V are the vertex vertices (or nodes, or points) of the graph G, the elements of E are its edge edges (or lines). The usual way to picture a graph is by drawing a dot for each vertex and joining two of these dots by a line if the corresponding two vertices form an edge. Just how these dots and lines are drawn is considered irrelevant: all that matters is the information of which pairs of vertices form an edge and which do not. 1 2 3 4 5 6 7 Fig. 1.1.1. The graph on V = { 1,..., 7 } with edge set E = {{ 1, 2 }, { 1, 5 }, { 2, 5 }, { 3, 4 }, { 5, 7 }} on A graph with vertex set V is said to be a graph on V . The vertex V (G), E(G) set of a graph G is referred to as V (G), its edge set as E(G). These conventions are independent of any actual names of these two sets: the vertex set W of a graph H = (W, F) is still referred to as V (H), not as W(H). We shall not always distinguish strictly between a graph and its vertex or edge set. For example, we may speak of a vertex v ∈ G (rather than v ∈ V (G)), an edge e ∈ G, and so on. order The number of vertices of a graph G is its order , written as |G|; its |G|, G number of edges is denoted by G . Graphs are finite, infinite, countable and so on according to their order. Except in Chapter 8, our graphs will be finite unless otherwise stated. ∅ For the empty graph (∅, ∅) we simply write ∅. A graph of order 0 or 1 is called trivial. Sometimes, e.g. to start an induction, trivial graphs can trivial graph be useful; at other times they form silly counterexamples and become a nuisance. To avoid cluttering the text with non-triviality conditions, we shall mostly treat the trivial graphs, and particularly the empty graph ∅, with generous disregard. incident A vertex v is incident with an edge e if v ∈ e; then e is an edge at v. ends The two vertices incident with an edge are its endvertices or ends, and an edge joins its ends. An edge { x, y } is usually written as xy (or yx). If x ∈ X and y ∈ Y , then xy is an X–Y edge. The set of all X–Y edges E(X, Y ) in a set E is denoted by E(X, Y ); instead of E({ x }, Y ) and E(X, { y }) we simply write E(x, Y ) and E(X, y). The set of all the edges in E at a E(v) vertex v is denoted by E(v)
31.1 GraphsTwo vertices r, y of G are adjacent, or neighbours, if ry 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 completecompletegraph on n vertices is a K"; a K3 is called a triangle.K"Pairwise non-adjacent vertices or edges are called independent.penateMore formally, a set of vertices or of edges is independent (or stable)if notwoof itselementsareadjacentLet G = (V,E) and G' - (V', E') be two graphs. We call G andG' isomorphic, and write G ~ G', if there exists a bijection p: V_ ViRwith ry e E p(r)p(y) e E' for all r,y e V. Such a map p is calledisomor-an isomorphism; if G = G', it is called an automorphism. We do notphismnormally distinguish between isomorphic graphs. Thus, we usually writeG - G' rather than G ~ G', speak of the complete graph on 17 vertices,and so on.A class of graphs that is closed under isomorphism is called 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 graphinuariant if it assigns equal values to isomorphic graphs. The numberinvariantof vertices and the number of edges of agraph are two simple graphinvariants:thegreatestnumber of pairwise adjacent verticesisanother14G'1..423°.5GUG'G-G'GnG'. Union, difference and intersection; the vertices 2,3,4Fig. 1.1.2.induce (or span) a triangle in GUG' but not in GWe set GuG':=(VUV',EuE')and GnG':=(VnV',EnE')GnG!If GnG' = O, then G and G' are disjoint. If V'V and E'C E, then subgraphG' is a subgraph of G (and G a supergraph of G'), written as G' C GG'CGLess formally, we say that G contains G'. If G' G and G' + G, thenG' is a proper subgraph of GIf G' C G and G' contains all the edges ry e E with r, y e V', theninducecG' is an induced subgraph of G; we say that V'induces or spans G' in G,subgraph
1.1 Graphs 3 Two vertices x, y of G are adjacent, or neighbours, if xy 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 (or stable) independent if no two of its elements are adjacent. Let G = (V,E) and G = (V , E ) be two graphs. We call G and G isomorphic, and write G G , if there exists a bijection ϕ: V → V with xy ∈ E ⇔ ϕ(x)ϕ(y) ∈ E for all x, y ∈ V . Such a map ϕ is called an isomorphism; if G = G , it is called an automorphism. We do not isomorphism 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. 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. 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 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 subgraph G is a subgraph of G (and G a supergraph of G ), written as G ⊆ G. G ⊆ G Less formally, we say that G contains G . If G ⊆ G and G = G, then G is a proper subgraph of G. 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
1.TheBasics生区口口Fig. 1.1.3. A graph G with subgraphs G' and G":G'is an induced subgraphof G, but G"is notand write G' =: G[v']. Thus if U C V is any set of vertices, then G[U]G[U]denotes the graph on U whose edges are precisely the edges of G withboth ends in U.If H is a subgraph of G, not necessarily induced, weabbreviate G[V(H)] to G[H]. Finally, G'CG is a spanning subgraphspanningof G if V' spans allof G, ie. if V' = V.TfTTisany set of vertices (usually of G), we write G-U forG[VU]. In other words, G-U is obtained from G by deleting all thevertices in UnV and their incident edges. If U -- [u] is a singleton, rather than G-(u). Instead of G-V(G') we simplywewriteG.write G-G'. For a subset F of [VP we write G-F := (V, E<F) and+G+F := (V, EUF); as above, G- fel and G+{el are abbreviated toedge-G-e and G+e. We call G edge-marimal with a given graph propertymaximalif G itself has the property but no graph G + ry does, for non-adjacentvertices r, y e GMore generally, when we call a graph minimal or marimal with someminimalproperty but have not specified any particular ordering, we are referringmaximalto the subgraph relation. When we speak of minimal or maximal sets ofvertices or edges, the reference is simply to set inclusionG*G'If G and G' are disjoint, we denote by G* G' the graph obtainedfrom GUG' by joining all the vertices of G to all the vertices of G'.Forcomple-example, K?+ K3 - K5. The complement G of G is the graph on Vment Gwith edge set [V?~E. The line graph L(G) of G is the graph on E inline graphwhich a,y e E are adjacent as vertices if and only if they are adjacentL(G)asedgesinGFig. 1.1.4.A graph isomorphic to its complement
4 1. The Basics 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 and write G =: G [ V G [ U ] ]. Thus if U ⊆ V is any set of vertices, then 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 G + xy does, for non-adjacent vertices x, y ∈ G. 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