not_has_induced_k4_subdivision_bot
The empty graph on any vertex type contains no induced subdivision of K4.
Statement
theorem not_has_induced_k4_subdivision_bot (V : Type*) : ¬ has_induced_k4_subdivision (⊥ : SimpleGraph V)
- Source
- Helper for arXiv:2610.32404 Proposition 11.2 (PR-412).
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- has_induced_k4_subdivisionA graph G contains an induced subdivision of K4: there are four distinct branch vertices and one simple path for each of their six…
The proof, explained
The proof proceeds by contradiction: an induced subdivision of K₄ in the empty graph would require four distinct vertices connected by walks. In particular, there would be a walk between the branch vertices b(0) and b(1). In the empty graph, however, reachable vertices must be identical, forcing b(0) = b(1), which contradicts the injectivity of the vertex embedding.
Assume for contradiction that the empty graph contains an induced subdivision of K₄.
Unpacking the definition of an induced K₄ subdivision produces an injective mapping b : Fin 4 → V for the four branch vertices, along with a family of walks P connecting each pair b(i) and b(j) for i < j.
rintro ⟨b, hb, P, _⟩
The branch vertices b(0) and b(1) must be equal.
Since 0 < 1 (checked by decide), the subdivision provides a walk in the empty graph ⊥ between b(0) and b(1), so they are mutually reachable. By SimpleGraph.reachable_bot.mp, any two reachable vertices in the empty graph must be identical.
uses
SimpleGraph.reachable_bot.mphave h : b 0 = b 1 := SimpleGraph.reachable_bot.mp ⟨P ⟨(0, 1), by decide⟩⟩
The equality b(0) = b(1) yields a contradiction. automation
Applying injectivity of b to b(0) = b(1) yields 0 = 1 in Fin 4. The norm_num tactic reduces this false numerical equality to False, completing the contradiction.
have := hb h norm_num at this
SimpleGraph.reachable_bot.mp- In the empty graph ⊥, if two vertices are connected by a walk, they must be equal.
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.
theorem not_has_induced_k4_subdivision_bot (V : Type*) : ¬ has_induced_k4_subdivision (⊥ : SimpleGraph V) := by rintro ⟨b, hb, P, _⟩ have h : b 0 = b 1 := SimpleGraph.reachable_bot.mp ⟨P ⟨(0, 1), by decide⟩⟩ have := hb h norm_num at this