In graph theory, what is a spanning tree of a connected, undirected graph?

Introduction / Context:
Spanning trees are fundamental concepts in graph theory and are widely used in network design, routing, and optimisation algorithms. Given a connected, undirected graph, a spanning tree is a special kind of subgraph that connects all vertices without forming cycles. Understanding this definition is essential for studying algorithms such as minimum spanning tree algorithms and for answering basic graph theory questions in interviews and exams.

Given Data / Assumptions:

• The original graph is connected and undirected, meaning there is at least one path between every pair of vertices.
• A subgraph is a graph formed from a subset of the vertices and edges of the original graph.
• A tree is a connected acyclic graph.
• The question asks specifically what qualifies as a spanning tree.

Concept / Approach:
A spanning tree of a connected, undirected graph is a subgraph that satisfies three conditions. First, it includes all vertices of the original graph, so it spans the graph. Second, it is connected, meaning there is a unique simple path between any pair of vertices. Third, it contains no cycles, so it is a tree. Because it has all vertices and is acyclic, a spanning tree of a graph with n vertices always has exactly n minus 1 edges. There can be many different spanning trees for a given graph, and algorithms such as Kruskal or Prim find minimum cost spanning trees when edges have weights.

Step-by-Step Solution:
Step 1: Recall that a tree is defined as a connected, acyclic graph. Step 2: Remember that spanning means including all vertices of the original graph. Step 3: Combine these ideas to define a spanning tree as a subgraph that contains all vertices, is connected, and has no cycles. Step 4: Examine option a, which states that a spanning tree is a subgraph including all vertices, connected, and cycle free, matching the definition. Step 5: Reject other options that either allow cycles, exclude vertices, or add new vertices that were not in the original graph.

Verification / Alternative check:
Consider a simple connected graph with four vertices and five edges that form a cycle. By removing one edge from the cycle while keeping all vertices connected, we obtain a subgraph with four vertices and three edges, no cycles, and connectivity between all vertices. This subgraph is a spanning tree. Checking the conditions shows that it includes all vertices, is connected, and has no cycles, reinforcing the definition given in option a.

Why Other Options Are Wrong:
Option b allows subgraphs that contain cycles and may exclude some vertices, which violates both the tree and spanning requirements. Option c describes a directed acyclic graph formed by orienting edges, which may not include all vertices in a tree structure and is not the standard definition of a spanning tree. Option d suggests adding extra vertices beyond those in the original graph, which contradicts the idea that a spanning tree is a subgraph of the original graph.

Common Pitfalls:
A common mistake is to think any tree that can be drawn using some of the vertices is a spanning tree, even if it omits vertices. Another pitfall is forgetting that spanning trees are defined for connected graphs; if the original graph is disconnected, a spanning tree does not exist, but a spanning forest may. For exam questions, always verify three properties: all original vertices, connectivity, and absence of cycles.

Final Answer:
A spanning tree is a subgraph that includes all the vertices of the original graph, is connected, and contains no cycles.