Spanning tree

Mathematical statement

Use a complete finite simple parent graph and a selected edge subgraph. Check edge membership, all parent vertices, connectivity and acyclicity. Connectivity plus n−1 edges, or acyclicity plus n−1 edges, certifies a tree; n−1 edges alone do not. Retain the one-vertex case and make no weighted or minimum-spanning-tree claim.

Representative formula (exact TeX)

T(G)

Assumptions

• The finite undirected loop-free simple parent graph is complete.
• Edges are selected by original parent-edge indices.

Symbol scope

• T — spanning tree
• G — parent graph

Intuition, definition, and misconceptions

Keep every parent vertex.

The selected edge subgraph must be a tree.

n−1 edges alone are insufficient; a single vertex is allowed, and a minimum-weight claim is not inferred.

Counting n−1 edges does not by itself prove a tree, and a spanning tree is not automatically a weighted-MST certificate.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Nonempty finite trees: connectivity, cycles, and unique paths — The selected full-vertex subgraph must be connected and acyclic.
• Finite simple undirected graphs — The parent and its subgraph are explicit.
• Connected component — The parent connectivity obligation is separate.

Verification boundary

Only complete finite unweighted graphs are handled.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Add minimum spanning trees.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.