AFTD Auto-Formalizing Theoretical Domains

is_chordal_bot

theoremverified

The edgeless graph on any vertex type is chordal.

Statement

theorem is_chordal_bot (V : Type*) : is_chordal (⊥ : SimpleGraph V)
Source
folklore
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • is_chordalA simple graph G is chordal if it contains no induced cycle of length four or greater.

Read back from the Lean

For any type V, the edgeless simple graph on V (the bottom element ⊥ : SimpleGraph V) is chordal (i.e., satisfies is_chordal).

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

A graph is chordal if it contains no induced cycle of length four or more. To show that the empty (edgeless) graph $\bot$ is chordal, we assume for contradiction that some cycle graph $C_n$ ($n \ge 4$) embeds into $\bot$ as an induced subgraph. Any such cycle contains an edge (between vertices $0$ and $1$), and an induced embedding must preserve edges, forcing an edge to exist in $\bot$. This contradicts the fact that the empty graph has no edges.

  1. Assume for contradiction that a cycle graph $C_n$ of length $n \ge 4$ is an induced subgraph of $\bot$, and write $n = m + 4$.

    By definition of chordality (`is_chordal`), we must prove that no cycle graph $C_n$ with $n \ge 4$ embeds into $\bot$ as an induced subgraph. We assume for contradiction that there is an induced embedding $f : C_n \hookrightarrow_g \bot$. Since $n \ge 4$, linear arithmetic allows us to express the cycle length as $n = m + 4$ for $m = n - 4$.

    lines 3–5

      intro n hn h
      rcases h with ⟨f⟩
      obtain ⟨m, rfl⟩ : ∃ m, n = m + 4 := ⟨n - 4, by omega⟩
  2. Vertices $0$ and $1$ are adjacent in the cycle graph $C_{m+4}$.

    In the cycle graph $C_{m+4}$, two vertices $u$ and $v$ in $\text{Fin}(m+4)$ are adjacent if and only if $u - v = 1$ or $v - u = 1$. For $u = 0$ and $v = 1$, we select the second branch $1 - 0 = 1$. Since $m + 4 \ge 4$, this equality holds in $\text{Fin}(m+4)$.

    lines 6–10

      have h01 : (SimpleGraph.cycleGraph (m + 4)).Adj (0 : Fin (m + 4)) (1 : Fin (m + 4)) := by
        change ((0 : Fin (m + 4)) - 1 = 1 ∨ (1 : Fin (m + 4)) - 0 = 1)
        right
        ext
        simp
  3. The embedding forces an edge in $\bot$, producing a contradiction.

    Because $f$ is an induced embedding, it preserves adjacency by `SimpleGraph.Embedding.map_adj_iff`, implying that $f(0)$ and $f(1)$ must be adjacent in $\bot$. However, the empty graph $\bot$ contains no edges, so this adjacency simplifies to False, completing the proof.

    lines 11–12

    uses SimpleGraph.Embedding.map_adj_iff

      have := (SimpleGraph.Embedding.map_adj_iff f).mpr h01
      simpa using this
SimpleGraph.Embedding.map_adj_iff
An induced subgraph embedding $f : G \hookrightarrow_g G'$ preserves and reflects adjacency: $f(v)$ and $f(w)$ are adjacent in $G'$ if and only if $v$ and $w$ are adjacent in $G$.

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

/-- The empty (edgeless) graph on any vertex type is chordal. -/theorem is_chordal_bot (V : Type*) : is_chordal (⊥ : SimpleGraph V) := by  intro n hn h  rcases h with ⟨f⟩  obtain ⟨m, rfl⟩ : ∃ m, n = m + 4 := ⟨n - 4, by omega⟩  have h01 : (SimpleGraph.cycleGraph (m + 4)).Adj (0 : Fin (m + 4)) (1 : Fin (m + 4)) := by    change ((0 : Fin (m + 4)) - 1 = 1 ∨ (1 : Fin (m + 4)) - 0 = 1)    right    ext    simp  have := (SimpleGraph.Embedding.map_adj_iff f).mpr h01  simpa using this
See it in the graphDiscuss this resultChallenge it