Questions: Trees and Spanning Trees

Question 1

A graph has 7 vertices and 6 edges. Is it necessarily a tree?

• A. Yes — any graph on n vertices with exactly n−1 edges is always a tree
• B. No — it could be disconnected and contain cycles, satisfying neither tree condition
• C. No — a tree on 7 vertices requires exactly 7 edges
• D. No — only graphs with n+1 edges can be connected

Answer: (B)

Having n−1 edges is necessary but not sufficient for a tree. A tree requires being connected AND acyclic; any two of those three properties (connected, acyclic, n−1 edges) imply the third. A graph on 7 vertices could have 6 edges but consist of a 3-cycle plus a 4-vertex path — disconnected and containing a cycle. Only when combined with connectivity or acyclicity does the edge count force a tree structure.

Question 2

A connected graph G has 8 vertices and many edges. You build a spanning tree of G. How many edges does the spanning tree have?

• A. It depends on which edges are in G
• B. 7 edges, regardless of G's structure
• C. 8 edges, one per vertex
• D. It depends on which spanning tree algorithm is used

Answer: (B)

Every spanning tree of a connected graph on n vertices has exactly n−1 edges — in this case 7. A spanning tree includes all n vertices and is itself a tree, so the n−1 edge count is guaranteed by the tree characterization. The specific edges chosen may vary (most graphs have many distinct spanning trees), but the count is always the same.

Question 3

Removing any single edge from a tree always disconnects it.

• T. True
• F. False

Answer: True

This is a direct consequence of the unique-path property. In a tree, there is exactly one path between any two vertices. Any edge (u, v) is the sole connection on the unique path between u and v. Remove it, and no path between u and v remains — the graph splits into two components. This is why trees are called 'minimally connected': they have just enough edges to stay connected, with no redundancy.

Question 4

A connected graph on n vertices has exactly one spanning tree.

• T. True
• F. False

Answer: False

Most connected graphs have many spanning trees — potentially exponentially many. Cayley's formula gives n^(n−2) labeled trees on n vertices, and a dense graph on n vertices contains all of them as possible spanning trees. For example, the complete graph K₄ has 4² = 16 distinct spanning trees. A graph has a unique spanning tree only if it is itself already a tree (removing any edge would disconnect it).

Question 5

Explain why any two of the three properties — connected, acyclic, has n−1 edges — imply the third for a graph on n vertices.

Model answer: If a graph is connected and acyclic, induction on n shows it has n−1 edges (remove a leaf, apply inductive hypothesis, restore). If it's connected with n−1 edges, any cycle would create a redundant edge — removing it would still leave the graph connected, meaning you could reach n vertices with n−2 edges, but connected acyclic graphs need exactly n−1, a contradiction. If it's acyclic with n−1 edges, a forest on n vertices with k components has n−k edges, so n−1 edges forces k=1, i.e., connectivity.

The equivalence is elegant: each pair of conditions pins down the third by a counting or path argument. The inductive proof (connected + acyclic → n−1 edges) is worth knowing: every tree has a leaf, removing it drops one vertex and one edge, and the remaining graph is still a tree by induction. The other directions use the fact that cycles introduce redundant connections and that a disconnected forest on n vertices always has fewer than n−1 edges.