For a network with n nodes, a spanning tree is
A) a set of (n-1) arcs that connects all nodes and contains no loops
B) a set of dummy arcs
C) a set of n arcs that connects all nodes
D) a random subset of arcs covering all nodes

Question

Quizplus · Accepted Answer

A spanning tree is a subset of graph G that contains all nodes of G and is a tree, i.e., it contains no cycles. For a network with n nodes, the maximum number of edges is n*(n-1)/2, but a tree with n nodes contains n-1 edges. Therefore, a spanning tree for a network with n nodes contains (n-1) edges, which is described by option A.

For a Network with N Nodes, a Spanning Tree Is