Which of the following is a necessary property of a spanning tree?

Options

  • A. It contains all vertices of the original graph
  • B. It must contain every edge of the original graph
  • C. It must contain at least one cycle
  • D. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

A. It contains all vertices of the original graph

Detailed Explanation

A spanning tree must contain every vertex of the original connected graph. However, it does not contain every edge because unnecessary edges may create cycles. A spanning tree is connected and acyclic and contains exactly N - 1 edges for N vertices. The word spanning refers to including all vertices, while tree means the resulting subgraph is connected and has no cycles.

← Previous Next →

Attempt Quiz Now:

BPSC TRE 4 DSA Practice set 1

Feature Posts