Every connected graph has a spanning tree
ProvedFamousTheorems.connected_graph_spanning_tree_7aEvery connected graph has a spanning tree. Let be a connected simple graph, possibly infinite. Then there is a subgraph on the same vertex set that is a tree.
For finite graphs a spanning tree is obtained by deleting edges from cycles until none remain, or by breadth-first search. For infinite graphs Zorn's lemma is needed. Spanning trees are basic in graph algorithms, in the definition of the fundamental group of a graph and in Kirchhoff's matrix-tree theorem.
Formalization note. Mathlib's SimpleGraph.Connected.exists_isTree_le. Subgraphs are simple graphs on the same vertex type ordered by inclusion of edge sets, so automatically spans all vertices. IsTree means connected and acyclic.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem connected_graph_spanning_tree_7a {V : Type*} {G : SimpleGraph V} (hG : G.Connected) : ∃ T ≤ G, T.IsTree := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `SimpleGraph.Connected.exists_isTree_le`. Proof here reduces to that Mathlib result.