Any spanning tree of a graph with |V| vertices has how many edges?
Aexactly |V| edges
Bexactly |E| − |V| + 1 edges
Cexactly 2|V| edges
Dexactly |V| − 1 edges
Answer & Solution
Correct answer: D. exactly |V| − 1 edges
A tree on n vertices has exactly n − 1 edges.
Any more would create a cycle (violating tree-ness)
any fewer would disconnect the graph (violating spanning).
So a spanning tree of |V| vertices has |V| − 1 edges.
The expression |E| − |V| + 1 is the cyclomatic complexity / circuit rank, not the tree size.
Keep practising Algorithms
Browse all Algorithms questions for GATE CSE, or explore more Computer Science topics.