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
- is_chordal_botThe edgeless graph on any vertex type is chordal.
- not_is_chordal_cycle_fourThe cycle graph C_4 on four vertices is not chordal.
- chordal_maxcut_optimal_strong_equilibrium_of_card_leFor every finite simple chordal graph G on at most 2k + 1 vertices and every integer k ≥ 3, the unweighted Max-k-Cut game admits an…
- chordal_maxcut_optimal_strong_equilibrium_of_max_degree_leFor every finite simple chordal graph G whose maximum degree is at most 2k - 1 and every integer k ≥ 3, the unweighted Max-k-Cut game…
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