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.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for