Proof of `Trees are outerplanar`
groundedproofs/Lax303502Proofs/Trees.lean · lax-303502
What this proof establishes
no assumptions
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
Every finite tree admits a straight-line drawing with all vertices on the unit circle, independently of the excluded-minor characterization.
Proof strategy
Induct on the number of vertices. A nontrivial finite tree has a leaf, and removing it leaves a tree. Keep the smaller tree's circle drawing and insert the leaf immediately after its neighbour in the parameter order. Finiteness provides a gap with no other vertex. The chord for the new edge strictly separates all other old vertices from the empty circular cap, so it misses every edge with disjoint endpoints. The same-circle tangent inequality rules out vertices lying on edges. Single-vertex trees are handled directly.
Attribution
Diestel, Graph Theory, sixth edition, Section 1.5, gives the leaf-removal induction. Chapter 4, Exercise 23, states the outerplanarity characterization but does not supply a direct drawing proof. As an additional source for the geometric construction, Pach and Törőcsik, Layout of rooted trees, CS-TR-369-92 (1992), page 2, Algorithm 1, recursively embed a tree into points in convex position. Here the specialization to a circle is implemented by leaf insertion and explicit rational coordinates; the separation algebra is proved in this submission.