AFTD Auto-Formalizing Theoretical Domains

not_is_chordal_cycle_four

theoremverified

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.

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

    line 3

      intro h
  2. This 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.

    line 4

    uses le_rfl, SimpleGraph.Embedding.refl

      exact 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

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