151.5 Trees and forests[9.2.1]Corollary 1.5.4. If T is a tree and G is any graph with (G) ≥ [T- 1,[9.2.3]then T C G, i.e. G has a subgraph isomorphic to T.Proof. Find a copy of T in G inductively along its vertex enumerationfrom Corollary 1.5.2.Sometimes it is convenient to consider one vertex of a tree as special;such a vertex is then called the root of this tree. A tree T with a fixedrootroot r is a rooted tree. Writing <y for e rTy then defines a partialordering on V(T), the tree-order associated with T and r. We shalltree-orderthink of this ordering as expressing height': if <y we say that r liesntabowbelow y in T, we calldown/below[yl :=[a l a≤y]and[], [][a]:=(y ly≥r]thedoclosureofyandthepcosurefandsoon.Notethat thedowlosureup-closureroot r isthe least element in this partial ordertheleaves of T areitsmaximal elements, the ends of any edge ofT are comparable,and thedown-closure of every vertex is a chain, a set of pairwise comparablechainelements. (Proofs?) The vertices at distance k from r have height k andheightform the kth level of T.levelA rooted tree T contained in a graph G is called normal in G ifnormal treethe ends of every T-path in G are comparable in the tree-order of TIf T spans G, this amounts to requiring that two vertices of T must becomparable whenever they are adjacent in G; see Figure 1.5.2.Fig.1.5.2.A normal spanning tree with root rA normal tree T in G can be a powerful tool for examining thestructure of G, because G reflects the separation properties of T:8.5.7Lemma 1.5.5. Let T be a normal tree in G.[8.5.8](i) Any two vertices , y e T are separated in G by the set [r]n[y](i) If S V(T) = V(G) and S is down-closed, then the componentsof G - S are spanned by the sets [r] with r minimal in T-S
1.5 Trees and forests 15 Corollary 1.5.4. If T is a tree and G is any graph with δ(G) |T| −1, [ 9.2.1 ] [ 9.2.3 ] then T ⊆ G, i.e. G has a subgraph isomorphic to T. Proof . Find a copy of T in G inductively along its vertex enumeration from Corollary 1.5.2. Sometimes it is convenient to consider one vertex of a tree as special; such a vertex is then called the root of this tree. A tree T with a fixed root root r is a rooted tree. Writing x y for x ∈ rTy then defines a partial ordering on V (T), the tree-order associated with T and r. We shall tree-order think of this ordering as expressing ‘height’: if x<y we say that x lies below y in T, we call up/above down/below y := { x | x y } and x := { y | y x } t, t the down-closure of y and the up-closure of x, and so on. Note that the down-closure up-closure root r is the least element in this partial order, the leaves of T are its maximal elements, the ends of any edge of T are comparable, and the down-closure of every vertex is a chain, a set of pairwise comparable chain elements. (Proofs?) The vertices at distance k from r have height k and height form the kth level of T. level A rooted tree T contained in a graph G is called normal in G if normal tree the ends of every T-path in G are comparable in the tree-order of T. If T spans G, this amounts to requiring that two vertices of T must be comparable whenever they are adjacent in G; see Figure 1.5.2. r G T Fig. 1.5.2. A normal spanning tree with root r A normal tree T in G can be a powerful tool for examining the structure of G, because G reflects the separation properties of T: Lemma 1.5.5. Let T be a normal tree in G. [ 8.2.3 ] [ 8.5.7 ] [ 8.5.8 ] (i) Any two vertices x, y ∈ T are separated in G by the set x∩y. (ii) If S ⊆ V (T) = V (G) and S is down-closed, then the components of G − S are spanned by the sets x with x minimal in T − S.
161.The BasicsProof. (i) Let P be any r-y path in G. Since T is normal, the vertices ofPin T form a sequence =ti,...,t = y for which t and ti+1 are alwayscomparable in the tree oder of T. Consider a minimal such sequence ofvertices in PnT. In this sequence we cannot have ti-1 < t, > ti+1for any i, since ti-1 and ti+1 would then be comparable and deleting twould yield a smaller such sequence. SoT=ti>..>t<.<tn =yfor some k e (1,...,n]. As t, e []n[y]nV(P), the result follows.(i) Since S is down-closed, the upper neighbours in T of any vertexof G - S are again in G - S (and clearly in the same component), sothe components C of G-S are up-closed. As S is down-closed, minimalvertices of C are also minimal in G -- S. By (), this means that C has口only one minimal vertex and equals its up-closure [r].Normal spanning trees are also called depth-first search trees, because of the way they arise in computer searches on graphs (Exercise 19).This fact is often used to prove their existence. The following inductiveproof, however, is simpler and lluminates nicely how normal trees capture the structure of their host graphs.[6.5.3]Proposition 1.5.6. Every connected graph contains a normal spanning[8.2.4]tree, with any specified vertex as its root.Proof. Let G be a connected graph and r e G any specified vertex. Let Tbe a maximal normal tree with root r in G; we show that V(T) = V(G).Suppose not, and let C be a component of G-T. As T is normal,N(C) is a chain in T. Let be its greatest element, and let y e C beadjacent to r. Let T' be the tree obtained from T by joining y to r; thetree-order of T' then extends that of T. We shall derive a contradictionby showing that T'is also normal in G.Let P be a T'-path in G. If the ends of P both lie in T, then theyare comparable in the tree-order of T (and hence in that of T'), becausethen P is also a T-path and T is normal in G by assumption. If notthen y is one end of P, so P lies in C except for its other end z, whichlies in N(C). Then z ≤ r, by the choice of r. For our proof that y andz are comparable it thus sufices to show that <y,ie. that erT'y.0This, however, is clear since y is a leaf of T' with neighbour r
16 1. The Basics Proof . (i) Let P be any x–y path in G. Since T is normal, the vertices of P in T form a sequence x = t1,...,tn = y for which ti and ti+1 are always comparable in the tree oder of T. Consider a minimal such sequence of vertices in P ∩ T. In this sequence we cannot have ti−1 < ti > ti+1 for any i, since ti−1 and ti+1 would then be comparable and deleting ti would yield a smaller such sequence. So x = t1 > ... > tk < ... < tn = y for some k ∈ { 1,...,n }. As tk ∈ x∩y ∩V (P), the result follows. (ii) Since S is down-closed, the upper neighbours in T of any vertex of G − S are again in G − S (and clearly in the same component), so the components C of G−S are up-closed. As S is down-closed, minimal vertices of C are also minimal in G − S. By (i), this means that C has only one minimal vertex x and equals its up-closure x. Normal spanning trees are also called depth-first search trees, because of the way they arise in computer searches on graphs (Exercise 19). This fact is often used to prove their existence. The following inductive proof, however, is simpler and illuminates nicely how normal trees capture the structure of their host graphs. Proposition 1.5.6. Every connected graph contains a normal spanning [ 6.5.3 ] [ 8.2.4 ] tree, with any specified vertex as its root. Proof . Let G be a connected graph and r ∈ G any specified vertex. Let T be a maximal normal tree with root r in G; we show that V (T) = V (G). Suppose not, and let C be a component of G − T. As T is normal, N(C) is a chain in T. Let x be its greatest element, and let y ∈ C be adjacent to x. Let T be the tree obtained from T by joining y to x; the tree-order of T then extends that of T. We shall derive a contradiction by showing that T is also normal in G. Let P be a T -path in G. If the ends of P both lie in T, then they are comparable in the tree-order of T (and hence in that of T ), because then P is also a T-path and T is normal in G by assumption. If not, then y is one end of P, so P lies in C except for its other end z, which lies in N(C). Then z x, by the choice of x. For our proof that y and z are comparable it thus suffices to show that x<y, i.e. that x ∈ rT y. This, however, is clear since y is a leaf of T with neighbour x.
171.6 Bipartite graphs1.6 Bipartite graphsLet r ≥ 2 be an integer. A graph G = (V.E) is called r-partite ifr-partiteV admits a partition into r classes such that every edge has its endsin different classes: vertices in the same partition class must not beadjacent. Instead of ‘2-partite' one usually says bipartite.bipartiteK2.2.2=K3Fig. 1.6.1. Two 3-partite graphsAn r-partite graph in which every two vertices from different parcompletetition classes are adjacent is called complete; the complete r-partiter-partitegraphs for all r together are the complete multipartite graphs.Thecomplete r-partite graph Kni *..* Kn, is denoted by Kn...n,; ifKn.nr- ng =: s, we abbreviate this to K,. Thus, K, is the completen1=.KTr-partite graph in which every partition class contains exactly s ver-tices.6 (Figure 1.6.1 shows the example of the octahedron K3; compareits drawing with that in Figure 1.4.3.) Graphs of the form K1,n arecalled stars; the vertex in the singleton partition class of this Ki.n is thestarstar's centre.centre·Fig. 1.6.2. Three drawings of the bipartite graph K3,3 = K?Clearly, a bipartitegraph cannot contain an odd cycle,a cycle ofoddodd cyclelength. In fact, the bipartite graphs are characterized by this property:[8.2]Proposition 1.6.1. A graph is bipartite if and only if it contains noodd cycle.6Note that we obtain a Ky if we replace each vertex of a Kr by an independentS-set; our notation of K, is intended to hint at this connection
1.6 Bipartite graphs 17 1.6 Bipartite graphs Let r 2 be an integer. A graph G = (V,E) is called r-partite if r-partite V admits a partition into r classes such that every edge has its ends in different classes: vertices in the same partition class must not be adjacent. Instead of ‘2-partite’ one usually says bipartite. bipartite K2,2,2 = K3 2 Fig. 1.6.1. Two 3-partite graphs An r-partite graph in which every two vertices from different partition classes are adjacent is called complete; the complete r-partite complete r-partite graphs for all r together are the complete multipartite graphs. The complete r-partite graph Kn1 ∗ ... ∗ Knr is denoted by Kn1,...,nr ; if Kn1,...,nr n1 = ... = nr =: s, we abbreviate this to Kr s . Thus, Kr s is the complete Kr s r-partite graph in which every partition class contains exactly s vertices.6 (Figure 1.6.1 shows the example of the octahedron K3 2 ; compare its drawing with that in Figure 1.4.3.) Graphs of the form K1,n are called stars; the vertex in the singleton partition class of this K1,n is the star star’s centre. centre = = Fig. 1.6.2. Three drawings of the bipartite graph K3,3 = K2 3 Clearly, a bipartite graph cannot contain an odd cycle, a cycle of odd odd cycle length. In fact, the bipartite graphs are characterized by this property: Proposition 1.6.1. A graph is bipartite if and only if it contains no [ 5.3.1 ] [ 6.4.2 ] odd cycle. 6 Note that we obtain a Kr s if we replace each vertex of a Kr by an independent s-set; our notation of Kr s is intended to hint at this connection.
181.The Basics(1.5.1)Proof. Let G = (V, E) be a graph without odd cycles: we show that G isbipartite. Clearly a graph is bipartite if all its components are bipartiteor trivial, so we may assume that G is connected. Let T be a spanningtree in G, pick a root r e T, and denote the associated tree-order on Vby <T. For each u e V, the unique path rTu has odd or even length.This defines a bipartition of V; we show that G is bipartite with thispartition.Fig. 1.6.3. The cycle Ce in T+Let e = ay be an edge of G. If e e T, with z <T y say, thenrTy = rTry and so r and y lie in different partition classes. If e Tthen Ce := rTy + e is a cycle (Fig. 1.6.3), and by the case treatedalready the vertices along rTy alternate between the two classes. SinceCe is even by assumption, r and y again lie in different classes.口1.7 Contraction and minorsIn Section 1.1 we saw two fundamental containment relations betweengraphs: the'subgraph' relation, and the‘induced subgraph'relation. Inthis section we meet two more: the 'minor' relation, and the 'topologicalminor' relation.G/eLet e = ry be an edge of a graph G = (V, E). By G/e we denote thecontraction graph obtained from G by contracting the edge e into a new vertex ve,which becomes adjacent to all the former neighbours of r and of y. For-mally, G/eis a graph (V',E') with vertex set V':-(V<(,y))U(ve)(where ve is the 'new' vertex, i.e. ve VUE) and edge setUeE' :- [oweEl(u,w]n(r,y] =0]U vew l aweE-fe] or yw eE[e]]
18 1. The Basics (1.5.1) Proof . Let G = (V,E) be a graph without odd cycles; we show that G is bipartite. Clearly a graph is bipartite if all its components are bipartite or trivial, so we may assume that G is connected. Let T be a spanning tree in G, pick a root r ∈ T, and denote the associated tree-order on V by T . For each v ∈ V , the unique path rTv has odd or even length. This defines a bipartition of V ; we show that G is bipartite with this partition. e Ce r x y Fig. 1.6.3. The cycle Ce in T + e Let e = xy be an edge of G. If e ∈ T, with x <T y say, then rTy = rT xy and so x and y lie in different partition classes. If e /∈ T then Ce := xT y + e is a cycle (Fig. 1.6.3), and by the case treated already the vertices along xT y alternate between the two classes. Since Ce is even by assumption, x and y again lie in different classes. 1.7 Contraction and minors In Section 1.1 we saw two fundamental containment relations between graphs: the ‘subgraph’ relation, and the ‘induced subgraph’ relation. In this section we meet two more: the ‘minor’ relation, and the ‘topological minor’ relation. G/e Let e = xy be an edge of a graph G = (V,E). By G/e we denote the contraction graph obtained from G by contracting the edge e into a new vertex ve, which becomes adjacent to all the former neighbours of x and of y. Formally, G/e is a graph (V , E ) with vertex set V := (V { x, y })∪ { ve } ve (where ve is the ‘new’ vertex, i.e. ve ∈/ V ∪ E) and edge set E := vw ∈ E | { v, w }∩{ x, y } = ∅ ∪ vew | xw ∈ E { e } or yw ∈ E { e } .
191.7-Contraction and minorsG/eFig. 1.7.1. Contracting the edge e =ryMore generally, if X is another graph and (V r e V(X)) is apartition of V into connected subsets such that, for any two verticesr,y e X, there is a V-Vy edge in G if and only if ry e E(X), we callMXG an MX and write7 G - MX (Fig. 1.7.2). The sets V, are the branchsets of this Mx. Intuitively, we obtain X from G by contracting everybranch setsbranch set to a single vertex and deleting any parallel edges' or 'loops'that may arise. In infinite graphs, branch sets are allowed to be infinite.For example, the graph shown in Figure 8.1.1 is an MX with X aninfinitestar.VGFig.1.7.2.YG=MX,soXisaminorof YIf Vr = U V is one of the branch sets above and every otherbranch set consists just of a single vertex, we also write G/U for theG/Ugraph X and uu for the vertex r e X to which U contracts, and thinkof the rest of X as an induced subgraph of G. The contraction of asingle edge uu' defined earlier can then be viewed as the special case ofU= (u,u'].Proposition 1.7.1. G is an Mx if and only if X can be obtainedfrom G by a series of edge contractions, i.e. if and only if there aregraphs Go,.-, Gn and edges ei e G, such that Go = G, Gn X, andGi+i = Gi/e; for all i < n.口Proof. Induction on |G| -[X].7 Thus formally, the expression MX-whereMstandsfor‘minor':seebelow-refers to a whole class of graphs, and G = MX means (with slight abuse of notation)that G belongs to this class
1.7 Contraction and minors 19 x y e ve G G/e Fig. 1.7.1. Contracting the edge e = xy More generally, if X is another graph and { Vx | x ∈ V (X) } is a partition of V into connected subsets such that, for any two vertices x, y ∈ X, there is a Vx–Vy edge in G if and only if xy ∈ E(X), we call G an MX and write7 G = MX (Fig. 1.7.2). The sets Vx are the branch MX sets of this MX. Intuitively, we obtain X from G by contracting every branch sets branch set to a single vertex and deleting any ‘parallel edges’ or ‘loops’ that may arise. In infinite graphs, branch sets are allowed to be infinite. For example, the graph shown in Figure 8.1.1 is an MX with X an infinite star. X Y Vx Vz x z G Fig. 1.7.2. Y ⊇ G = MX, so X is a minor of Y If Vx = U ⊆ V is one of the branch sets above and every other branch set consists just of a single vertex, we also write G/U for the G/U graph X and vU for the vertex x ∈ X to which U contracts, and think vU of the rest of X as an induced subgraph of G. The contraction of a single edge uu defined earlier can then be viewed as the special case of U = { u, u }. Proposition 1.7.1. G is an MX if and only if X can be obtained from G by a series of edge contractions, i.e. if and only if there are graphs G0,...,Gn and edges ei ∈ Gi such that G0 = G, Gn X, and Gi+1 = Gi/ei for all i<n. Proof . Induction on |G|−|X|. 7 Thus formally, the expression MX—where M stands for ‘minor’; see below— refers to a whole class of graphs, and G = MX means (with slight abuse of notation) that G belongs to this class.