HasHoleOfLengthAtLeast
def
A graph G has a hole of length at least t if, for some n with t ≤ n and n ≥ 4, G contains an induced copy of the cycle C_n on n vertices. (A hole is an induced cycle of length at least 4.)
Statement
def HasHoleOfLengthAtLeast {V : Type*} (G : SimpleGraph V) (t : ℕ) : Prop
- Source
- step towards op_292_cop_number_p6_claw_free
- Verified
- 25 Oct 2026
- Axioms
- none listed
Lean source view module on GitHub
/-- G has a hole (an induced cycle) of length at least `t`. -/ def HasHoleOfLengthAtLeast {V : Type*} (G : SimpleGraph V) (t : ℕ) : Prop := ∃ n : ℕ, t ≤ n ∧ 4 ≤ n ∧ SimpleGraph.IsIndContained (SimpleGraph.cycleGraph n) G