# Nonempty finite trees: connectivity, cycles, and unique paths

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

A finite simple undirected graph is a tree only when nonempty, connected, and acyclic; retain singleton, degree-one leaf, and new-edge cycle conventions.

mko-tree · concept · v0.10.0



## Mathematical statement

For a finite simple undirected graph G=(V,E), this entry defines a tree by nonempty V, connectivity between every pair of vertices, and absence of simple cycles. A path does not repeat vertices; the zero-edge path from a vertex to itself is valid. Every vertex pair in a tree has a unique path. A leaf here has degree exactly one.





## Representative formula (exact TeX)

T(V,E)





## Assumptions


- Exercises use at most ten distinct safe-integer labels in V; each member of E joins exactly two distinct vertices in V. Normalize undirected edge direction and repeated listings. Loops, absent endpoints, and multigraph semantics are excluded.
- The empty graph is not a tree. A singleton without edges is a tree, but its degree-zero vertex is not a degree-one leaf, so its leaf list is empty.
- Adding an edge first requires a tree, distinct u,v in V, and no existing edge between them. The new edge and original unique path create one simple cycle; an already existing edge does not meet this premise.





## Symbol scope


- T — finite nonempty-tree predicate
- V — set of distinct vertices
- E — simple undirected edge set





## Intuition, definition, and misconceptions

The equation |E|=|V|−1 alone does not prove that a graph is a tree: a triangle plus an isolated vertex has this count but is disconnected. Empty and singleton cases use explicit conventions, not a visual guess.

Output the unique path in actual vertex order, not as a sorted set. For a new-edge cycle, begin at the smaller endpoint label, follow the original path to the larger endpoint, then close along the new edge. List degree-one leaves in increasing order; general tree theorems still require formalization.

Common errors include deciding from edge count alone, calling a degree-zero singleton a degree-one leaf, or treating a repeated existing edge as a new cycle.





## Adopted derivation guide

[Trees: deciding that a 6-vertex graph is a tree, with its leaves, a unique path and the unique cycle after adding an edge](https://ocme.evemisslab.com/en/derivations/derivation-mko-tree-01/)The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.





## Prerequisites


- [Finite simple undirected graphs](https://ocme.evemisslab.com/en/mko/mko-graph/) — Fix loop-free, duplicate-normalized undirected edge-set semantics.





## Verification boundary

Finite graph instances can be recomputed completely; general tree equivalence theorems and formal Evidence are not established.

not_formalized

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





## Next obligation

Bind pinned SimpleGraph.IsTree with its nonempty Connected condition, unique paths, degree-one leaves, and cycles from adding nonadjacent edges.





## 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/tree.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-tree/index.md)