is_linear_forest_bot
The empty simple graph on any vertex type is a linear forest.
Statement
theorem is_linear_forest_bot {V : Type*} : is_linear_forest (⊥ : SimpleGraph V)
- Source
- folklore
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- is_linear_forestA simple graph is a linear forest if it is acyclic and every vertex has at most two neighbors.
- simple_graph_power_oneG^1 = G.
Read back from the Lean
For any type V, the empty simple graph ⊥ : SimpleGraph V (the graph on V with no edges) is a linear forest.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To show that the empty graph ⊥ on any vertex type is a linear forest, we unfold the definition of a linear forest into acyclicity and a maximum degree of at most 2. The empty graph contains no edges, so it is acyclic. Moreover, every vertex has an empty neighbor set with cardinality 0 ≤ 2, which completes the proof.
The empty simple graph ⊥ is a linear forest. automation
Unfolding the definition of `is_linear_forest`, we must show that the empty graph ⊥ is acyclic and that the cardinality of the neighbor set of every vertex is at most 2. Automation (via `simp` / `simpa`) establishes both facts: the empty graph has no edges and hence no cycles, and the neighbor set of every vertex is empty, which has cardinality 0 ≤ 2.
uses
is_linear_forest,simple_graph_power_onetheorem is_linear_forest_bot {V : Type*} : is_linear_forest (⊥ : SimpleGraph V) := by first | exact simple_graph_power_one | (apply simple_graph_power_one <;> assumption) | (apply simple_graph_power_one <;> simp_all) | simpa using simple_graph_power_one | (simp only [is_linear_forest] at *; first | exact simple_graph_power_one | (apply simple_graph_power_one <;> assumption) | (apply simple_graph_power_one <;> simp_all) | simpa using simple_graph_power_one)
is_linear_forest- A simple graph is a linear forest if it is acyclic and every vertex has degree (neighbor set cardinality) at most 2.
simple_graph_power_one- The first graph power of a simple graph G equals G.
- The proof script is structured as an automated search with fallback alternatives (`first | ...`). The successful branch unfolds `is_linear_forest` and invokes `simpa using simple_graph_power_one`. The simplifier closes both conditions directly from basic properties of the empty graph (acyclicity and empty neighbor sets), leaving the passed lemma `simple_graph_power_one` unused in the mathematical reduction.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The empty simple graph on any vertex type is a linear forest. -/theorem is_linear_forest_bot {V : Type*} : is_linear_forest (⊥ : SimpleGraph V) := by first | exact simple_graph_power_one | (apply simple_graph_power_one <;> assumption) | (apply simple_graph_power_one <;> simp_all) | simpa using simple_graph_power_one | (simp only [is_linear_forest] at *; first | exact simple_graph_power_one | (apply simple_graph_power_one <;> assumption) | (apply simple_graph_power_one <;> simp_all) | simpa using simple_graph_power_one)