Start learning →

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.
Practise this question with Quill — GATE CSE →

Keep practising Algorithms

Browse all Algorithms questions for GATE CSE, or explore more Computer Science topics.

Start a Algorithms lesson →
Related questions