Questions: Trees, Forests, and Spanning Trees

Question 1

A connected graph has 10 vertices. Alice removes edges one at a time, always keeping the graph connected, until no more edges can be removed without disconnecting it. How many edges remain?

• A. 10 — one edge per vertex is needed for connectivity
• B. 9 — she has constructed a spanning tree with n − 1 edges
• C. It depends on the original graph — different graphs require different minimum edge counts
• D. At least 10 — a connected graph must have at least as many edges as vertices

Answer: (B)

Any connected graph on n vertices can be reduced to a spanning tree by removing edges while maintaining connectivity. A spanning tree is the minimally connected spanning subgraph, and every tree on n vertices has exactly n − 1 edges — no more, no less. The result is always 9 for 10 vertices, regardless of the original graph's structure.

Question 2

In a tree on 8 vertices, how many distinct simple paths exist between any given pair of vertices?

• A. It depends on the structure of the tree — some trees have more paths than others
• B. 0 — trees have no cycles, so you cannot traverse between vertices
• C. Exactly 1 — the acyclic condition guarantees a unique path between every pair
• D. At least 2 — every connected graph provides multiple routes

Answer: (C)

The unique-path property is one of the most important consequences of a tree's definition. If there were two distinct simple paths from u to v, tracing one path forward and the other backward would form a cycle — but trees are acyclic by definition. This contradiction proves the path must be unique. This uniqueness is why trees are the natural data structure for hierarchical indexing, file systems, and shortest-path computations.

Question 3

A forest with 15 vertices and 4 connected components has exactly 11 edges.

• T. True
• F. False

Answer: True

A forest's edge count follows the formula: edges = vertices − components = n − k. Here, 15 − 4 = 11. Each connected component is a tree with (vertices in component − 1) edges, and summing over all components yields n − k total edges. This generalizes the tree formula: a tree is just a forest with k = 1 component, giving n − 1 edges.

Question 4

In any tree with more than one vertex, nearly every vertex has degree at least 2.

• T. True
• F. False

Answer: False

Trees always have leaf nodes — vertices of degree 1. In fact, any tree with at least 2 vertices has at least 2 leaves. You can see this by considering the path between any two most-distant vertices: the endpoints of this longest path must be leaves (if a leaf had degree 2 or more, you could extend the path further, contradicting maximality). Claiming every vertex has degree ≥ 2 would imply the graph contains a cycle, which trees cannot.

Question 5

Why is there exactly one path between any two vertices in a tree? Explain the argument.

Model answer: A tree is acyclic. If there were two distinct simple paths from vertex u to vertex v, you could follow one path from u to v and return along the other — tracing a closed walk. Removing any shared prefix and suffix would isolate a cycle. But trees have no cycles, so this is impossible. Therefore, the path must be unique.

This argument uses a proof by contradiction: assume two paths exist, derive a cycle, contradict the acyclic requirement. The uniqueness property has deep practical consequences — it means trees provide unambiguous routing, which is why spanning trees underlie network topology, parse trees, and minimum-path algorithms.