131.4 Connectivity[133Theorem 1.4.3. (Mader 1972)Let 0 + k e N. Every graph G with d(G) ≥ 4k has a (k+1)-connectedsubgraph H such that e(H) > e(G) - k(13)Proof. Put := e(G) (≥ 2k), and consider the subgraphs G' C G suchAthatJG'I≥ 2k and G'l >(IG'I-k)(*)Such graphs G' exist since G is one; let H be one of smallest orderHlo graph G' as in (+) can have order exactly 2k, since this wouldimply that G'll > k ≥ 2k? > (IG'l). The mimality of H thereforeimplies that (H) >: othericould delete a vertex of degree atmost and obta1 a graph G' C H still satisfying (*). In particular, wehave [H] ≥ . Dividing the inequality of |H >[H|-k from (*) by[H| therefore yields e(H) >- k, as desiredIt remains to show that H is (k + 1)-connected. If not, then Hhas a proper separation [Ui,U2] of order at most k; put H[U] =: H,H1,H2Since any vertex u eUUa has all its d()≥(H)>neighboursfromHinHi.wehave[Hil≥≥2k.Similarly.[Hl≥2k.Asbytheminimality of H neither Hi nor H2 satisfies (*), we further haveH≤ (H)-K)for i = 1, 2. But thenH≤HI+H2≤ (IHiI+[H2] -2k)≤(IH)-k)(as |HinH2/ ≤k),which contradicts (+) for H.口1.5 Trees and forestsAn acyclic graph, es.is called a forest.Acforesto011ngalnectedoresticalledatree(Thusorestisagraphwhoecomponentsrare trees.) The vertices of degree I in a tree are its leaves, the othersare its inner vertices. Every non-trivial tree has a leafconsider, forexample, the ends of a longest path. This little fact often comes inhandy, especially in induction proofs about trees: if we remove a leaffrom a tree, what remains is still a tree.except that theroot ofatree (seebelow) is nevercalled a leaf, evenifit hasdegree 1
1.4 Connectivity 13 Theorem 1.4.3. (Mader 1972) [7.2.3] [11.2.3] Let 0 = k ∈ N. Every graph G with d(G) 4k has a (k + 1)-connected subgraph H such that ε(H) > ε(G) − k. Proof. Put γ := ε(G) ( 2k), and consider the subgraphs G ⊆ G such (1.2.2) (1.3.1) γ that |G | 2k and G > γ |G | − k . (∗) Such graphs G exist since G is one; let H be one of smallest order. H No graph G as in (∗) can have order exactly 2k, since this would imply that G > γk 2k2 > |G | 2 . The minimality of H therefore implies that δ(H) > γ : otherwise we could delete a vertex of degree at most γ and obtain a graph G H still satisfying (∗). In particular, we have |H| γ. Dividing the inequality of H > γ |H| − γk from (∗) by |H| therefore yields ε(H) > γ − k, as desired. It remains to show that H is (k + 1)-connected. If not, then H has a proper separation {U1, U2} of order at most k; put H[Ui] =: Hi. H1, H2 Since any vertex v ∈ U1 U2 has all its d(v) δ(H) > γ neighbours from H in H1, we have |H1| γ 2k. Similarly, |H2| 2k. As by the minimality of H neither H1 nor H2 satisfies (∗), we further have Hi γ |Hi| − k for i = 1, 2. But then H H1 + H2 γ |H1| + |H2| − 2k γ |H| − k (as |H1 ∩ H2| k), which contradicts (∗) for H. 1.5 Trees and forests An acyclic graph, one not containing any cycles, is called a forest. A con- forest nected forest is called a tree. (Thus, a forest is a graph whose components tree are trees.) The vertices of degree 1 in a tree are its leaves, 5 the others leaf are its inner vertices. Every non-trivial tree has a leaf—consider, for example, the ends of a longest path. This little fact often comes in handy, especially in induction proofs about trees: if we remove a leaf from a tree, what remains is still a tree. 5 ... except that the root of a tree (see below) is never called a leaf, even if it has degree 1.
141. The BasicsFig. 1.5.1. A tree1.8.3Theorem 1.5.1. The following assertions are equivalent for a graph T:[4.2.9](i) T is a tree;(i) Any two vertices of T are linked by a unique path in T;(i) T is minimally connected, ie.T is connected but T-e is discon-iected for every edge e eT;(iv) T is maximally acyclic, i.e. T contains no cycle but T + ry doesor any two non-adjacent vertices ,y e T.BThe proof of Theorem 1.5.1 is straightforward, andd a good exerciseo1le not yet familiar with all the notions it relates. Extending ouraTynotation for paths from Section 1.3, we write rTy for the unique pathin a tree T between two vertices ,y (see (ii) above).A common application of Theorem 1.5.1 is that every connectedgraph contains a spanning tree: take a minimal connected spanning sub-graph and use (ii), or take a maximal acyclic subgraph and apply (iv).Figure 1.4.1 shows a spanning tree in each of the three coonontsof the graph depicted. When T is a spanning tree of G, the edges inchordE(G)<E(T) are the chords of T in G.Corollary 1.5.2. The vertices of a tree can always be enumerated, sayas vi,..., Un, so that every vi with i ≥ 2 has a unique neighbour in[01,..,Vi-1](1.4.1)Proof. Use the enumeration from Proposition 1.4.1.口Corollary 1.5.3. A connected graph with n vertices is a tree if andonly if it has n -1 edges.Proof.Inductio1 on i shows that the subgraph spanned by the firstvertices in Corollary 1.5.2 has i- 1 edges; for i = n this proves theforward implication. Conversely, let G be any connected graph with nvertices and n -1 edges. Let G' be a spanning tree in G. Since G' has口n-1edgesbythefirstimplication,itfollowsthatG=G
14 1. The Basics Fig. 1.5.1. A tree Theorem 1.5.1. The following assertions are equivalent for a graph T: [1.6.1] [1.9.5] [4.2.9] (i) T is a tree; (ii) Any two vertices of T are linked by a unique path in T; (iii) T is minimally connected, i.e. T is connected but T − e is disconnected for every edge e ∈ T; (iv) T is maximally acyclic, i.e. T contains no cycle but T + xy does, for any two non-adjacent vertices x, y ∈ T. The proof of Theorem 1.5.1 is straightforward, and a good exercise for anyone not yet familiar with all the notions it relates. Extending our xT y notation for paths from Section 1.3, we write xT y for the unique path in a tree T between two vertices x, y (see (ii) above). A common application of Theorem 1.5.1 is that every connected graph contains a spanning tree: take a minimal connected spanning subgraph and use (iii), or take a maximal acyclic subgraph and apply (iv). Figure 1.4.1 shows a spanning tree in each of the three components of the graph depicted. When T is a spanning tree of G, the edges in chord E(G) E(T) are the chords of T in G. Corollary 1.5.2. The vertices of a tree can always be enumerated, say as v1,...,vn, so that every vi with i 2 has a unique neighbour in {v1,...,vi−1}. (1.4.1) Proof. Use the enumeration from Proposition 1.4.1. [1.9.5] Corollary 1.5.3. A connected graph with n vertices is a tree if and [2.4.4] [4.2.9] only if it has n − 1 edges. Proof. Induction on i shows that the subgraph spanned by the first i vertices in Corollary 1.5.2 has i − 1 edges; for i = n this proves the forward implication. Conversely, let G be any connected graph with n vertices and n − 1 edges. Let G be a spanning tree in G. Since G has n − 1 edges by the first implication, it follows that G = G .
151.5 Trees and forests8323Corolla1.5.4.IfTisatreeand Gisany graph with (G) ≥ [T| - 1,then T C G, ie. G has a subgraph isomorphic to T.Proof. Find a copy of T in G inductively along its vertex enumerationfrom Corollary1.5.2口itiscoienttoevertex of atreeasspecialmsuch a vertex is then called the root of this tree. A tree T with a fixedrootroot r is a rooted tree. Writing r ≤ y for r 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 liesup/abovebelow y in T, we calldown/below[], ][l :=[la≤y] and [a] :=y [yr]the doun-closure of y and the up-closure of r, and so on. Aset X V(T) down-clup-clasurethat equals its up-closure, ie. which satisfies X - [X] :=Urexle], isclosed upwards, or an up-set in T. Similarly, there are down-closed sets.or down-sets etoNote that the root of T is the least element in its tree-order, theleaves alts maximal elements, the ends of any edge of T are comparable, and the down-closure of every vertex is a chain, a set of pairwisechaincomparableelements. (Proofs?)The vertices at distancekfrom theroothave height k and form the kth level of Theight, levelA rooted tree T contained in a graph G is called normal in G if normal 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.2Fig.1.5.2.A1norue'ootA normal tree T in G can be a powerful tool for examining thestructure of G, because G refects the separation properties of T:
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. A set X ⊆ V (T) down-closure up-closure that equals its up-closure, i.e. which satisfies X = X := x∈Xx, is closed upwards, or an up-set in T. Similarly, there are down-closed sets, or down-sets etc.. Note that the root of T is the least element in its tree-order, the leaves 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 chain comparable elements. (Proofs?) The vertices at distance k from the root have height k and form the kth level of T. height, 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:
161. The Basics8.8.8Lemma 1.5.5. Let T be a normal tree in G.(i) Any two vertices t,y eT are separated in G by the set [ln[>](i) If S V(T) = V(G) and S is down-closed, then the componentsofG-Sarespannedbythesetsrwithrminimal inT-S.Proof. (i) Let P bes[]n[y]-ypathinG:weshowthatPmLILet ti,..,tn be a minimal sequence of vertices in PnT such that ti -and tn = y and t, and ti+i are comparable in the tree-order of T forall i. (Such a sequence exists: the set of all vertices in PnT, in theirnatural order astheyoccur on P,has this propertybecauseT is normaland every segment tPti+i is either an edge of T or a T-path) In ourminimal sequence we cannot have ti-1 < t, > ti+1 for any i, sinceand ti+ would thenbe comparable,and deletingt, would yieldasmallersuch sequence. Thus, our sequence has the formT=t>..>t<...<t=yfor some k e [1...,n]. As t, e [r]n[ylnv(P), our proof is complete(i) Consider a component C of G - S, and let be a minimalelement of its vertex set. Then V(C) has no other milnal element r':as and would be incomparable, any r-a' path in C would by (i)contain a vertex below both, contradicting their minimality in V(C)Hence as every vertex of C lies above some minimalelement ofV(C),itlies above a. Conversely, every vertex y e [r] lies in C, for since S isdown-closed,theascending path Ty lies inS. Thus. V(C) = IrlLet us show that r is minimal not only in V(C) but also in T - SThe vertices belor form a chain [tl in T.As t is a neighbour of r.thelityofCasacompont of G-s implies that teS,giving[t] C S since S is down-closed. This completes the proof that everycomponent of G-S is spanned by a setrwith r minimal in T_S.Conversely, if r is any minimal element of T - S, it is clearly alsominimal in the component C of G- S to which it belongs.ThenV(C) = [] as before, ie., [3] spans this component.口Normal spanning trees are also called depth-first search trees, because of the way they arise in computer searches on graphs (Exercise 26)Thisfactisoften used to prove theirexistence,whichcan alsobeshownby a very short and clever induction (Exercise 25). The following con-structive proof, however, illuminates better how normal trees capturethe structure of their host graphs.[8.2]Proposition 1.5.6. Every connected graph contains a normal spanningtree, with any specified vertex as its root
16 1. The Basics Lemma 1.5.5. Let T be a normal tree in G. [8.2.3] [8.6.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. Proof. (i) Let P be any x–y path in G; we show that P meets x∩y. Let t1,...,tn be a minimal sequence of vertices in P ∩T such that t1 = x and tn = y and ti and ti+1 are comparable in the tree-order of T for all i. (Such a sequence exists: the set of all vertices in P ∩ T, in their natural order as they occur on P, has this property because T is normal and every segment tiP ti+1 is either an edge of T or a T- path.) In our minimal 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. Thus, our sequence has the form x = t1 > ... > tk < ... < tn = y for some k ∈ {1,...,n}. As tk ∈ x∩y ∩V (P), our proof is complete. (ii) Consider a component C of G − S, and let x be a minimal element of its vertex set. Then V (C) has no other minimal element x : as x and x would be incomparable, any x–x path in C would by (i) contain a vertex below both, contradicting their minimality in V (C). Hence as every vertex of C lies above some minimal element of V (C), it lies above x. Conversely, every vertex y ∈ x lies in C, for since S is down-closed, the ascending path xT y lies in T − S. Thus, V (C) = x. Let us show that x is minimal not only in V (C) but also in T − S. The vertices below x form a chain t in T. As t is a neighbour of x, the maximality of C as a component of G− S implies that t ∈ S, giving t ⊆ S since S is down-closed. This completes the proof that every component of G − S is spanned by a set x with x minimal in T − S. Conversely, if x is any minimal element of T − S, it is clearly also minimal in the component C of G − S to which it belongs. Then V (C) = x as before, i.e., x spans this component. Normal spanning trees are also called depth-first search trees, because of the way they arise in computer searches on graphs (Exercise 26). This fact is often used to prove their existence, which can also be shown by a very short and clever induction (Exercise 25). The following constructive proof, however, illuminates better 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.
171.5 TreessandforestsProoLetGbed 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 r be its greatest element, and let y e C beadjacent to z. 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 Tis also noormalinG'-path in G. If theends of P both lie in T, then theyLetPbarableinthetree-orderofT(andhce in thatofT'),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 suffices to show that < y, i.e. that r e rT'y.This, however, is clear since y is a leaf of T' with neighbour r.1.6 Bipartite graphsLet r ≥ 2 be an integer. A graph G = (V,E) is called r-partite ifr-partiteV admits a partition into r claes 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 bipartitebipartiteXDK2.2.2 = K3Fig. 1.6.1, Two 3-partite graphAn r-partite graph in which every two vertices from different par-eapitetition classes are adjacent is called complete; the complete r-partitegraphs for all r together are the complete multipartite graphs. Thecomplete r-partite graph Kni **Knr is denoted by Knr.Kni..:fs, we abbreviate this to K,. Thus, K, is the completeKT21r-partite graph in which every partition class contains exactly s ver-tices.6 (Figure 1.6.1 shows the eample of the octahedron K2;compareits drawing with that in Figure 1.4.3.) Graphs of the form Ki1.n are6Note that weobtain a Ky if wereplace each vertex of a Kr by an independents-set; our notation of Kr is intended to hint atthis connection
1.5 Trees and forests 17 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. 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 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.