AFTD Auto-Formalizing Theoretical Domains

not_has_induced_k4_subdivision_bot

theoremverified

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.

  1. 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.

    line 3

      rintro ⟨b, hb, P, _⟩
  2. 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.

    line 4

    uses SimpleGraph.reachable_bot.mp

      have h : b 0 = b 1 := SimpleGraph.reachable_bot.mp ⟨P ⟨(0, 1), by decide⟩⟩
  3. 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.

    lines 5–6

      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

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
See it in the graphDiscuss this resultChallenge it