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-S1.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.