AFTD Auto-Formalizing Theoretical Domains

has_induced_k4_subdivision_top

theoremverified

The complete graph on four vertices contains an induced subdivision of K4, using the six single-edge paths.

Statement

theorem has_induced_k4_subdivision_top :
    has_induced_k4_subdivision (⊤ : SimpleGraph (Fin 4))
Source
Helper for arXiv:2610.32404 Proposition 11.2 (PR-412).
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

The proof, explained

The complete graph on four vertices is itself isomorphic to K4, so it contains an induced subdivision where no edges are subdivided. We witness this by taking the identity map on Fin 4 for the branch vertices and the six single-edge walks between pairs with i < j as the paths. Each single-edge walk is a path with no internal vertices, and every vertex of Fin 4 is already a branch vertex. Finally, every edge between vertices x and y corresponds to the path indexed by the ordered pair (min(x, y), max(x, y)), showing that the subdivision is induced.

  1. Define the branch vertex embedding as the identity and each path as a single-edge walk, leaving four subdivision conditions to verify.

    For each pair of vertices i < j in Fin 4, the strict inequality implies i ≠ j by ne_of_lt, so the vertices are adjacent in the complete graph ⊤ by SimpleGraph.top_adj. Turning each such edge into a length-1 walk yields a family of walks P. We then instantiate has_induced_k4_subdivision using the identity map on Fin 4 (which is injective by Function.injective_id) and the family P, generating four subgoals corresponding to the definition of an induced subdivision.

    lines 3–7

    uses SimpleGraph.top_adj, ne_of_lt, Function.injective_id

      let P : (e : {ij : Fin 4 × Fin 4 // ij.1 < ij.2}) →
          (⊤ : SimpleGraph (Fin 4)).Walk e.val.1 e.val.2 :=
        fun e => (show (⊤ : SimpleGraph (Fin 4)).Adj e.val.1 e.val.2 from
          (SimpleGraph.top_adj _ _).mpr (ne_of_lt e.property)).toWalk
      refine ⟨id, Function.injective_id, P, ?_, ?_, ?_, ?_⟩
  2. Each walk P(e) is a path.

    Because each walk P(e) is constructed from a single edge connecting adjacent endpoints, SimpleGraph.Adj.isPath_toWalk proves that it contains no repeated vertices and is therefore a path.

    lines 8–9

    uses SimpleGraph.Adj.isPath_toWalk

      · intro e
        exact SimpleGraph.Adj.isPath_toWalk _
  3. The only branch vertices on P(e) are its endpoints.

    The vertex support of a single-edge walk consists solely of its starting and ending vertices. Consequently, any vertex on the walk is necessarily one of the two endpoints.

    lines 10–11

      · intro e i hi
        simpa [P] using hi
  4. Any vertex shared by two distinct paths is a branch vertex.

    Because the branch vertices are all of Fin 4 via the identity map, every vertex v in the graph is already a branch vertex, witnessed by v itself since v = id(v).

    lines 12–13

      · intro e f hef v hve hvf
        exact ⟨v, rfl⟩
  5. Every edge between vertices of the subdivision is an edge of one of the paths.

    Let x and y be adjacent vertices in the complete graph. Irreflexivity of adjacency implies x ≠ y. By totality of the order on Fin 4 (lt_or_gt_of_ne), either x < y or y < x. If x < y, the edge s(x, y) is the single edge of the path P(x, y). If y < x, the symmetry of unordered pairs (Sym2.eq_swap) gives s(x, y) = s(y, x), which is the edge of P(y, x).

    lines 14–18

    uses lt_or_gt_of_ne, Sym2.eq_swap

      · intro x y hx hy hxy
        have hne : x ≠ y := hxy.ne
        rcases lt_or_gt_of_ne hne with hlt | hgt
        · exact ⟨⟨(x,y), hlt⟩, by simp [P]⟩
        · exact ⟨⟨(y,x), hgt⟩, by simp [P, Sym2.eq_swap]⟩
SimpleGraph.top_adj
In the complete simple graph, two vertices are adjacent if and only if they are distinct.
ne_of_lt
In a preorder, a strictly smaller element is not equal to a larger element.
Function.injective_id
The identity function is injective.
SimpleGraph.Adj.isPath_toWalk
A walk formed by traversing a single edge between adjacent vertices is a path.
lt_or_gt_of_ne
In a linear order, two distinct elements satisfy either a < b or b < a.
Sym2.eq_swap
An unordered pair is symmetric: s(a, b) = s(b, a).

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 has_induced_k4_subdivision_top :    has_induced_k4_subdivision (⊤ : SimpleGraph (Fin 4)) := by  let P : (e : {ij : Fin 4 × Fin 4 // ij.1 < ij.2}) →      (⊤ : SimpleGraph (Fin 4)).Walk e.val.1 e.val.2 :=    fun e => (show (⊤ : SimpleGraph (Fin 4)).Adj e.val.1 e.val.2 from      (SimpleGraph.top_adj _ _).mpr (ne_of_lt e.property)).toWalk  refine ⟨id, Function.injective_id, P, ?_, ?_, ?_, ?_⟩  · intro e    exact SimpleGraph.Adj.isPath_toWalk _  · intro e i hi    simpa [P] using hi  · intro e f hef v hve hvf    exact ⟨v, rfl⟩  · intro x y hx hy hxy    have hne : x ≠ y := hxy.ne    rcases lt_or_gt_of_ne hne with hlt | hgt    · exact ⟨⟨(x,y), hlt⟩, by simp [P]⟩    · exact ⟨⟨(y,x), hgt⟩, by simp [P, Sym2.eq_swap]⟩
See it in the graphDiscuss this resultChallenge it