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