Trees and spanning trees

Trees, forests and the one-vertex case

Use the finite simple-graph setting throughout these theorems, with n ≥ 1. A tree is connected and acyclic. A forest is acyclic but may have several components, including isolated vertices. K₁ is a tree with one vertex and no edges. A triangle plus an isolated vertex is not a tree, even though it has n−1 edges

1. 1Tree convention A tree is a nonempty finite connected acyclic simple graph. The one-vertex zero-edge graph is a tree
2. 2Edge count A tree on n vertices has n−1 edges; this is a theorem, not the definition

Why every nontrivial tree has a leaf

In a finite tree with at least two vertices, choose a longest simple path. An endpoint has a neighbour along the path. If it had another neighbour outside the path, the path could be extended; if that neighbour were elsewhere on the path, it would create a cycle. Both are impossible, so the endpoint has degree one. The same argument applies to the other endpoint. Removing a leaf and its incident edge leaves a tree: paths between remaining vertices cannot use the leaf internally, and deletion cannot create a cycle

Prove the tree edge count by induction

Base n=1: the tree has zero edges, equal to n−1. Assume every k-vertex tree has k−1 edges. For an arbitrary (k+1)-vertex tree, remove a leaf as justified above. The remaining k-vertex graph is a tree and has k−1 edges by the hypothesis. Restoring the one removed edge gives k edges, equal to (k+1)−1. Induction proves the count for every integer n≥1

Derive the forest component count

Suppose the c components have vertex counts n₁,…,n_c. Each component is connected and acyclic, hence a tree, including one-vertex components. The proved tree count gives n_i−1 edges in component i. Adding over all components gives e=(n₁+…+n_c)−c=n−c. For an empty forest, n=e=c=0 also satisfies this count, although the tree equivalences are stated only for n≥1

Equivalent condition: a unique simple path

A tree is connected, so a simple path exists between each pair of distinct vertices. Two different simple paths would diverge and later rejoin; the two distinct segments between such common vertices form a cycle. Thus the path is unique. Conversely, if every pair has exactly one simple path, the graph is connected. A cycle would offer two different paths between adjacent cycle vertices, contradicting uniqueness. Therefore the graph is acyclic and is a tree

Equivalent condition: connected with n−1 edges

A tree is connected and has n−1 edges by the proved count. Conversely, take a connected simple graph with n−1 edges. If it has a cycle, delete a cycle edge; connectedness is preserved. Repeating finitely many times yields a connected acyclic spanning graph, a tree on the same n vertices. If any deletion occurred, it would have fewer than n−1 edges, contradicting the tree count. No cycle existed, so the original graph is a tree

Equivalent condition: acyclic with n−1 edges

A tree is acyclic and has the proved edge count. Conversely, an acyclic graph is a forest. If e=n−1, its component formula e=n−c gives c=1. It is therefore connected as well as acyclic and hence a tree. This is where the acyclic hypothesis is used; do not replace it by an assumption that the graph is already a tree

The displayed triangle plus isolated D has four vertices and three edges. What does it demonstrate?

Written tree proof (ungraded)

Write a complete proof that a finite simple forest with n≥1 vertices and n−1 edges is a tree. State the component-count result you use, show why there is exactly one component and conclude from the definition

Model proof using the forest count

Let c be the number of components. Since the graph is a forest, e=n−c. The hypothesis e=n−1 gives n−c=n−1, hence c=1. Thus the forest is connected; it is already acyclic and simple, and is nonempty. By the definition it is a tree. This argument cites the fully proved forest count rather than assuming the conclusion

What makes a tree spanning

A spanning tree of a parent graph uses all its vertices and a subset of its edges, and is itself connected and acyclic. Every finite connected simple graph has one: repeatedly remove cycle edges without losing connectedness until none remain. If the parent has n vertices and e edges, a spanning tree keeps n−1 edges, so e−(n−1) edges are removed. This is unweighted structural reasoning, not a minimum-length optimisation

What should you check first when deciding whether an edge set is a spanning tree?

A spanning tree has 6 vertices. Calculate its required number of edges

The source graph has 8 edges. Calculate how many edges are removed to leave the 5-edge spanning tree

Using n edges instead of n - 1. One of these lines is right. Which one?