AFTD Auto-Formalizing Theoretical Domains

is_chordal

def

A simple graph G is chordal if it contains no induced cycle of length four or greater.

Statement

def is_chordal {V : Type*} (G : SimpleGraph V) : Prop
Defined in
Dirac (1961), On rigid circuit graphs
Verified
27 Oct 2026
Axioms
none listed
Used by 4

Read back from the Lean

For an arbitrary type V and a simple graph G on V, is_chordal G is defined to hold if and only if for every natural number n, if 4 ≤ n, then the cycle graph SimpleGraph.cycleGraph n is not contained as an induced subgraph in G (that is, ¬ SimpleGraph.IsIndContained (SimpleGraph.cycleGraph n) G).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- A simple graph is chordal if it has no induced cycle of length at least 4. -/
def is_chordal {V : Type*} (G : SimpleGraph V) : Prop :=
  ∀ n : ℕ, 4 ≤ n → ¬ SimpleGraph.IsIndContained (SimpleGraph.cycleGraph n) G
See it in the graphDiscuss this resultChallenge it