What is a spanning tree?

• A. A subgraph with all edges.
• B. A disconnected graph.
• C. A connected acyclic subgraph that includes all vertices.
• D. A cycle that spans all vertices.

Answer: (C)

A spanning tree is a subset of the graph’s edges that keeps every vertex present, but connects them all without forming any cycle. In a graph with n vertices, such a subgraph has exactly n−1 edges, making it a minimal way to stay connected.

That description matches the statement: a connected acyclic subgraph that includes all vertices. It includes all vertices while remaining connected and without cycles, which is exactly what a spanning tree is.

The other ideas fall short: taking all edges can create cycles and isn’t necessarily minimal; a disconnected subgraph isn’t connected; a cycle that spans all vertices is connected and spans all vertices but contains a cycle, so it isn’t a tree.