Trees

Result 1. Proof. A tree with two or more vertices has an edge, and a path repeats no vertex, so there are finitely many paths and a longest one, (v_0, \ldots, v_k), has k \ge 1. A neighbor w \ne v_{k-1} of v_k would either be some v_i with i \le k - 2, closing the cycle (v_i, \ldots, v_k, v_i), or lie off the path and extend it. Both are impossible, so \deg(v_k) = 1, and likewise \deg(v_0) = 1. \square

Result 2. Proof. T - \ell has no cycle, since T has none. A vertex strictly inside a path has two neighbors on it, so a path in T between two vertices other than \ell avoids \ell and lies in T - \ell. \square

Result 3. Proof. By induction on n. A one-vertex tree has 0 edges. Suppose every tree with k \ge 1 vertices has k - 1 edges, and let T have k + 1. By Result 1 it has a leaf \ell; by Result 2, T - \ell is a tree with k vertices and so k - 1 edges; T has one edge more, k in all. \square The step shrinks an arbitrary tree. Growing a tree by adding a leaf would prove the count only for the trees built that way.

Result 4. Proof. The components are trees with n_1 + \cdots + n_c = n vertices, and every edge lies in one (Walks, paths, cycles and connected graphs, Result 2), so there are (n_1 - 1) + \cdots + (n_c - 1) = n - c edges. \square

Result 5. Proof. In a tree T two vertices are joined by a walk, and a walk contains a path with the same ends (Walks, paths, cycles and connected graphs, Result 1). Suppose two different paths P, Q from u to v exist, chosen with the least total length. Then u \ne v, since (u) is the only path from u to u. If they shared a vertex w \ne u, v, splitting both at w would give a pair of different paths with smaller total length. So they meet only at u and v, their lengths add to at least 3, and P followed by Q backward is a cycle: impossible.

Conversely, if every two vertices are joined by exactly one path, G is connected, and a cycle (v_0, v_1, \ldots, v_{k-1}, v_0) would give two paths (v_0, v_1) and (v_0, v_{k-1}, \ldots, v_1). \square

Result 6. Proof. By Result 5 the only path from x to y is (x, y), so T - xy does not join them. For any w, the path from w to x either avoids xy or ends with the step from y to x, so w is joined to x or to y in T - xy: exactly two components, each with no cycle.

A cycle of T + uv uses uv, and the rest of it is a path from v to u in T, of which there is exactly one, of length at least 2. \square

Result 7. Proof. First a fact: if e = xy lies on a cycle (x, y, w_1, \ldots, w_m, x) of a connected graph, then removing e keeps it connected, since any walk can replace a step along e by (y, w_1, \ldots, w_m, x) or its reverse.

(a) and (b) give (c) by Result 3. (b) and (c): by Result 4, n - c = n - 1, so c = 1. (a) and (c): if G had a cycle, remove edges on cycles one at a time until none is left. The graph stays connected, so it ends as a tree on n vertices with fewer than n - 1 edges, against Result 3. \square

Result 8. Proof. The removal process of Result 7 turns a connected G into a tree on its n vertices, keeping n - 1 of its edges and removing one exactly when G has a cycle. For c components, add the bounds for each. \square

Result 9. Proof. By the handshake lemma (Degree, the handshake lemma and complete graphs, Result 1) and Result 3 the degrees add to 2n - 2. For n \ge 2 no vertex is isolated, so \sum_i n_i = n and \sum_i i\, n_i = 2n - 2. Subtracting twice the first gives \sum_i (i - 2)\, n_i = -2, where the i = 1 term is -n_1 and the i = 2 term is 0. \square

Result 10. Proof. The path from r to v \ne r is unique, so v has one parent. For an edge xy, let P be the path from r to x. If y is off P, then P followed by y is the path to y, and x is the parent of y. If y is on P, the part of P from y to x and the path (y, x) coincide by Result 5, so y is the parent of x. \square

Result 11. Stated without proof; Keller and Trotter, Section 5.6, give one. Example 7 and Exercises 19 and 20 check small cases.

1. (a) A tree, the path (1, 2, \ldots, 7). (b) Neither: (1, 3, 5, 1) is a cycle. It has 6 = 7 - 1 edges but components \{1, 3, 5\} and \{2, 4, 6, 7\}, failing two conditions of Result 7. (c) A forest, components \{1, 2, 3, 4, 7\} and \{5, 6\}, with 5 = 7 - 2 edges.
2. 56 edges (Result 3); 57 - c = 49 gives 8 components (Result 4).
3. 12 - 4 = 8 edges. At most 11 leaves: three single edges and a star of 6 vertices give 11. A tree whose s vertices are all leaves has degree sum s = 2s - 2, so s = 2, and 12 leaves would need six components.
4. (g, e, b, a, c, f, i), so d(g, i) = 6.
5. The cycle (d, j, f, c, a, b, d). Filling in cf leaves \{a, b, c, d, e, g, h\} and \{f, i, j\}.
6. With no cycle it would be a forest with some c \ge 1 components and n - c \le n - 1 edges (Result 4), fewer than n. Example: the triangle 12, 13, 23 and the path 34, 45, 56, 67, 78, with 3 + 5 = 8 edges. Removing any one path edge disconnects the graph, so by the fact in the proof of Result 7 none lies on a cycle: the triangle is the only one.
7. A cycle of T - v would be one of T. For w \ne v, the path from w to v reaches v from a neighbor x_i, so w is joined to x_i in T - v: at most d components. For neighbors x_i \ne x_j the only path in T is (x_i, v, x_j), so they are not joined in T - v: exactly d. \square
8. An edge on a cycle could be removed keeping the graph connected (the fact in the proof of Result 7), so it has no cycle, and being connected it is a tree. \square
9. If u, v were in different components, they are not adjacent, and a cycle of G + uv would need a path from v to u in G. So G is connected, and a tree. \square
10. The walk contains a path from u to v made of its edges (Walks, paths, cycles and connected graphs, Result 1), and by Result 5 that is the path from u to v. \square
11. 6. A connected network on 26 towns keeps at least 25 roads (Result 8), so at most 31 - 25 = 6 close, and removing roads on cycles reaches 25. What is left is a tree.
12. At least 9, since 31 \ge 40 - c (Result 8). Exactly 9 when it has no cycle, since then it is a forest with 40 - 31 = 9 components.
13. 27 atoms and \displaystyle \frac{4 \cdot 9 + 18}{2} = 27 bonds, more than the 26 of a tree, so the connected graph has a cycle by Result 7. (Cyclononane is such a ring.)
14. 2 \cdot 7 + 2 = 16 hydrogens, 23 atoms and 22 bonds. Only the two end carbons have one carbon neighbor, so 2, and 2 \cdot 3 + 5 \cdot 2 = 16.
15. n_1 = 2 + 1 \cdot 4 + 3 \cdot 2 = 12 leaves, 4 + 2 + 12 = 18 vertices.
16. n_1 = n_3 + 2 and n_1 + n_3 = 20 give 9 of degree 3 and 11 leaves. Always n = 2n_3 + 2, which is even.
17. A triangle and a separate edge: 5 vertices, 4 edges, no isolated vertex, a cycle.
18. Level 0: f; level 1: c, i, j; level 2: a; level 3: b; level 4: d, e; level 5: g, h. The parent of a is c, the children of b are d, e, and the height is 5. Root a gives height 3, the least: d(g, i) = 6 \le d(g, r) + d(r, i), so from any root r one of g, i is at level at least 3.
19. 6^{4} = 1296. Removing leaf 5 leaves a labeled tree on \{1, 2, 3, 4\} (Result 2), from one of whose 4 vertices 5 hangs; the 16 \cdot 4 = 64 choices give different trees and every such tree arises.
20. The 3 stars with center 2, 3 or 4, and the 3! = 6 paths (1, x, y, z): 9 in all. The method of Exercise 19 gives 3 \cdot 3 = 9.
21. For k \le 2, Result 1 gives two leaves. For k \ge 3, Result 9 gives n_1 \ge 2 + (k - 2) = k. \square
22. By induction on n; for n = 2 the single edge 12 works. For n \ge 3 some d_i = 1 (else the sum is at least 2n) and some d_j \ge 2 (else it is n < 2n - 2). Dropping d_i and lowering d_j by 1 leaves n - 1 positive integers with sum 2n - 4 = 2(n - 1) - 2; a tree on the other n - 1 labels with those degrees exists by hypothesis (after renaming labels), and joining i to j adds a leaf, which keeps a tree and finishes. \square
23. Both children are on level L + 1 if the parent is on level L, and by Result 10 the ends of an edge differ by one level. \square