# Spanning tree

This English edition is an AI candidate and does not yet have an OCME Atlas (GPT-6) Twin closure receipt.

A spanning tree is a connected acyclic subgraph containing every vertex of its parent graph.

mko-spanning-tree · definition · v0.10.0



## 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

[A spanning tree inside a square parent graph](https://ocme.evemisslab.com/en/derivations/derivation-mko-spanning-tree-01/)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](https://ocme.evemisslab.com/en/mko/mko-tree/) — The selected full-vertex subgraph must be connected and acyclic.
- [Finite simple undirected graphs](https://ocme.evemisslab.com/en/mko/mko-graph/) — The parent and its subgraph are explicit.
- [Connected component](https://ocme.evemisslab.com/en/mko/mko-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.

[Canonical MKO JSON](https://ocme.evemisslab.com/data/mko/spanning-tree.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-spanning-tree/index.md)