Question

A connected undirected graph has 8 vertices and 12 edges. How many edges will its spanning tree contain?

• A. 6
• B. 7
• C. 8
• D. 12

Hint:

If you ever see a graph with $n$ vertices and $n-1$ edges that is connected, it is a tree. If you add even one more edge, you create a cycle. If you remove even one edge, the graph becomes disconnected.

Answer 1

The Correct Option is B

Concept: A spanning tree of a graph is a subgraph that includes all the vertices of the original graph and is a tree (meaning it is connected and has no cycles).
• Property of Trees: Any tree with $V$ vertices must have exactly $V - 1$ edges.
• Connectedness: For a graph to be connected, it must have at least $V - 1$ edges.

Step 1: Identifying the number of vertices.
From the question, the graph has: \[ V = 8 \text{ vertices} \]

Step 2: Applying the tree property.
By definition, a spanning tree must connect all $V$ vertices using the minimum number of edges possible without forming a cycle. This number is always $V - 1$. \[ \text{Edges in spanning tree} = V - 1 \]

Step 3: Calculating the final value.
Substitute $V = 8$: \[ \text{Edges} = 8 - 1 = 7 \] The original 12 edges in the graph are irrelevant except to guarantee that a spanning tree can exist; the spanning tree itself will always use exactly 7 of those edges.