How many arcs are required to make a spanning tree in a network with n nodes and m arcs?
A) n
B) n − 1
C) m
D) m − 1

Question

Quizplus · Accepted Answer

A spanning tree is a connected acyclic subgraph of the original graph that includes all of the vertices. For a graph with n nodes, a spanning tree will have n-1 arcs. Therefore, the answer is (B) n-1 as this is the number of arcs required to make a spanning tree in a network with n nodes.

How Many Arcs Are Required to Make a Spanning Tree