GRAPH THEORY { LECTURE 4: TREES

1 GRAPH THEORY LECTURE 4: TREES . Abstract. presents some standard characterizations and properties of TREES . presents several different types of TREES . develops a counting method based on a bijection between labeled TREES and numeric strings. showns how binary TREES can be counted by the Catalan recursion. Outline Characterizations and Properties of TREES Rooted TREES , Ordered TREES , and Binary TREES Counting Labeled TREES : Pru fer Encoding Counting Binary TREES : Catalan Recursion 1. 2 GRAPH THEORY LECTURE 4: TREES . 1. Characterizations of TREES Review from tree = connected GRAPH with no cycles.

2 Def In an undirected tree, a leaf is a vertex of degree 1. Basic Properties of TREES . Proposition Every tree with at least one edge has at least two leaves. Proof. Let P = hv1, v2, .. , vmi be a path of maximum length in a tree T . Etc.. v3. v1. v2 vm w v3. v1 w vm v2. Figure : The two cases in the proof of Prop GRAPH THEORY LECTURE 4: TREES 3. Corollary If the minimum degree of a GRAPH is at least 2, then that GRAPH must contain a cycle. Proposition Every tree on n vertices has exactly n 1 edges. Proof. By induction using Prop . Review from An acyclic GRAPH is called a forest.

3 Review from The number of components of a GRAPH G is de- noted c(G). Corollary A forest G on n vertices has n c(G) edges. Proof. Apply Prop to each of the components of G.. Corollary Any GRAPH G on n vertices has at least n c(G) edges. 4 GRAPH THEORY LECTURE 4: TREES . Six Different Characterizations of a Tree TREES have many possible characterizations, and each contributes to the structural understanding of graphs in a different way. The following theorem establishes some of the most useful characterizations. Theorem Let T be a GRAPH with n vertices. Then the following statements are equivalent.

4 (1) T is a tree. (2) T contains no cycles and has n 1 edges. (3) T is connected and has n 1 edges. (4) T is connected, and every edge is a cut-edge. (5) Any two vertices of T are connected by exactly one path. (6) T contains no cycles, and for any new edge e, the GRAPH T + e has exactly one cycle. Proof. See text.. GRAPH THEORY LECTURE 4: TREES 5. The Center of a Tree Review from and The eccentricity of a vertex v in a GRAPH G, denoted ecc(v), is the distance from v to a vertex farthest from v. That is, ecc(v) = max{d(v, x)}. x VG. A central vertex of a GRAPH is a vertex with minimum eccentricity.

5 The center of a GRAPH G, denoted Z(G), is the subgraph induced on the set of central vertices of G. In an arbitrary GRAPH G, the center Z(G) can be anything from a single vertex to all of G. 6 GRAPH THEORY LECTURE 4: TREES . However, C. Jordan showed in 1869 that the center of a tree has only two possible cases. We begin with some preliminary results concerning the eccentricity of vertices in a tree. Lemma Let T be a tree with at least three vertices. (a) If v is a leaf of T and w is its neighbor, then ecc(w) = ecc(v) 1. (b) If u is a central vertex of T , then deg(u) 2.

6 Proof. (a) Since T has at least three vertices, deg(w) 2. Then there exists a vertex z 6= v such that d(w, z) = ecc(w). v w z Figure : But z is also a vertex farthest from v, and hence ecc(v) = d(v, z) = d(w, z) + 1 = ecc(w) + 1. (b) By Part (a), a vertex of degree 1 cannot have minimum eccentricity in tree T , and hence, cannot be a central vertex of T .. GRAPH THEORY LECTURE 4: TREES 7. Lemma Let v and w be two vertices in a tree T such that w is of maximum distance from v ( , ecc(v) = d(v, w)). Then w is a leaf. Proof. Let P be the unique v-w path in tree T . If deg(w) 2, then w would have a neighbor z whose distance from v would equal d(v, w) + 1, contradicting the premise that w is at maximum distance.

7 P. T. z w v Figure : 8 GRAPH THEORY LECTURE 4: TREES . Lemma Let T be a tree with at least three vertices, and let T . be the subtree of T obtained by deleting from T all its leaves. If v is a vertex of T , then eccT (v) = eccT (v) + 1. Proof. Let w be a vertex of T such that eccT (v) = d(v, w). By Lemma , vertex w is a leaf of tree T and hence, w 6 VT (as illustrated in Figure ). It follows that the neighbor of w, say z, is a vertex of T that is farthest from v among all vertices in T , that is, eccT (v) = d(v, z). Thus, eccT (v) = d(v, w) = d(v, z) + 1 = eccT (v) + 1.

8 W z T*. v T. Figure : GRAPH THEORY LECTURE 4: TREES 9. Proposition Let T be a tree with at least three vertices, and let T be the subtree of T obtained by deleting from T all its leaves. Then Z(T ) = Z(T ). Proof. From the two preceding lemmas, we see that deleting all the leaves decreases the eccentricity of every remaining vertex by 1. It follows that the resulting tree has the same center.. Corollary (Jordan, 1869). Let T be an n-vertex tree. Then the center Z(G) is either a single vertex or a single edge. Proof. The assertion is trivially true for n = 1 and n = 2.

9 The result follows by induction, using Proposition . 10 GRAPH THEORY LECTURE 4: TREES . Tree Isomorphisms and Automorphisms Example The two graphs in Fig have the same degree sequence, but they can be readily seen to be non-isom in several ways. For instance, the center of the left GRAPH is a single vertex, but the center of the right GRAPH is a single edge. Also, the two graphs have unequal diameters. Figure : Why are these TREES non-isomorphic? GRAPH THEORY LECTURE 4: TREES 11. Example The GRAPH shown in Figure below does not have a non- trivial automorphism because the three leaves are all different distances from the center, and hence, an automorphism must map each of them to itself.

10 Figure : A tree that has no non-trivial automorphisms. Remark There is a linear-time algorithm for testing the isomorphism of two TREES (see [AhHoUl74, p84]). 12 GRAPH THEORY LECTURE 4: TREES . 2. Rooted, Ordered, Binary TREES Rooted TREES Def A directed tree is a directed GRAPH whose underlying GRAPH is a tree. Def A rooted tree is a tree with a designated vertex called the root. Each edge is implicitly directed away from the root. r r Figure : Two common ways of drawing a rooted tree. GRAPH THEORY LECTURE 4: TREES 13. Rooted Tree Terminology Designating a root imposes a hierarchy on the vertices of a rooted tree, according to their distance from that root.