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, be￾cause 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 cap￾ture 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.