141.The BasicsFig. 1.5.1.A tree[180]Theorem 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:(ii) T is minimally connected, i.e. T is connected but T-e is discon-nected for every edge e e T;(iv) T is maximally acyclic, i.e. T contains no cycle but T+ ry does.口for any two non-adjacent vertices a, y e T.The proof of Theorem 1.5.1 is straightforward, and a good exercisefor anyone not yet familiar with all the notions it relates,Extending ournotation for paths from Section 1.3, we write rTy for the unique pathrTyin a tree T between two vertices z,y (see (i) above).A frequently used application of Theorem 1.5.1 is that every con-nected graph contains a spanning tree: by the equivalence of (i) and (ii)any minimal connected spanning subgraph will be a tree. Figure 1.4.1shows a spanning tree in each of the three components of the graphdepicted.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[u.....Ui--].口(1.4.1)Proof. Use the enumeration from Proposition 1.4.1.[2.9.0]Corollary 1.5.3. A connected graph with n vertices is a tree if and[2.4.4]only if it has n-1 edges.[4.2.9]Proof. Induction on shows that the subgraph spanned by the firsti vertices 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' hasn -1 edges by the first implication, it follows that G = 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.6 ] [ 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 discon￾nected 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 frequently used application of Theorem 1.5.1 is that every con￾nected graph contains a spanning tree: by the equivalence of (i) and (iii), any minimal connected spanning subgraph will be a tree. Figure 1.4.1 shows a spanning tree in each of the three components of the graph depicted. 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.
Corollary 1.5.3. A connected graph with n vertices is a tree if and [ 1.9.6 ] [ 2.4.1 ] [ 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 .