AFTD Auto-Formalizing Theoretical Domains

has_no_induced_even_cycle

def

A simple graph G contains no induced even cycle if for every even integer n ≥ 4, G contains no induced subgraph isomorphic to the cycle graph C_n.

Statement

def has_no_induced_even_cycle {V : Type*} (G : SimpleGraph V) : Prop
Defined in
arXiv:2611.17885 Problem 2
Verified
16 Nov 2026
Axioms
none listed

Read back from the Lean

For a simple graph $G$ on a type of vertices $V$, has_no_induced_even_cycle G asserts that for every natural number $n$, if $4 \le n$ and $n$ is even, then the cycle graph on $n$ vertices (SimpleGraph.cycleGraph n) is not an induced subgraph of $G$ (i.e., not 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 has no induced even cycle if it contains no induced cycle of length 2m with 2m ≥ 4. -/
def has_no_induced_even_cycle {V : Type*} (G : SimpleGraph V) : Prop := ∀ n : ℕ, 4 ≤ n → Even n → ¬ SimpleGraph.IsIndContained (SimpleGraph.cycleGraph n) G
See it in the graphDiscuss this resultChallenge it