not_is_chordal_cycle_four
The cycle graph C_4 on four vertices is not chordal.
Statement
theorem not_is_chordal_cycle_four : ¬ is_chordal (SimpleGraph.cycleGraph 4)- 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
The cycle graph on 4 vertices (SimpleGraph.cycleGraph 4) is not chordal; that is, it is false that for all natural numbers $n \ge 4$, the cycle graph on $n$ vertices is not an induced subgraph of SimpleGraph.cycleGraph 4.
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
The proof proceeds by contradiction. By definition, a graph is chordal if it does not contain any cycle graph $C_n$ for $n \ge 4$ as an induced subgraph. If $C_4$ were chordal, it could not contain $C_4$ as an induced subgraph, which contradicts the fact that $C_4$ contains itself as an induced subgraph via the identity embedding.
Assume, for contradiction, that $C_4$ is chordal.
We introduce the hypothesis $h$ that the cycle graph $C_4$ is chordal, aiming to derive a contradiction.
intro hThis contradicts the fact that $C_4$ is an induced subgraph of itself.
By definition, a graph is chordal if it contains no induced cycle $C_n$ for $n \ge 4$. Instantiating this definition for $C_4$ at $n = 4$ with the trivial inequality $4 \le 4$ (via `le_rfl`) implies that $C_4$ cannot contain an induced copy of $C_4$. However, the identity embedding (`SimpleGraph.Embedding.refl`) directly witnesses that $C_4$ is an induced subgraph of itself, yielding False.
uses
le_rfl,SimpleGraph.Embedding.reflexact h 4 le_rfl ⟨SimpleGraph.Embedding.refl⟩
le_rfl- In any preorder, every element is less than or equal to itself: $a \le a$.
SimpleGraph.Embedding.refl- The identity induced subgraph embedding from any graph to itself ($G \hookrightarrow_g 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 4-cycle graph C_4 is not chordal. -/theorem not_is_chordal_cycle_four : ¬ is_chordal (SimpleGraph.cycleGraph 4) := by intro h exact h 4 le_rfl ⟨SimpleGraph.Embedding.refl⟩