is_chordal_bot
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.
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$.
intro n hn h rcases h with ⟨f⟩ obtain ⟨m, rfl⟩ : ∃ m, n = m + 4 := ⟨n - 4, by omega⟩
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)$.
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
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.
uses
SimpleGraph.Embedding.map_adj_iffhave := (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
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 (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