No two neighbours on a cycle avoiding the vertex
DefinitionSparseDisc_Supplement_NoTwoNeighboursOnAvoidingCyclegraph-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-discrepancy
A graph has this property if no vertex has two distinct neighbours that both lie on one cycle whose vertex set avoids .
Definition code
import Mathlib
namespace SparseDisc.Supplement
/-- No vertex has two distinct neighbours lying on a cycle that avoids it, the graph condition in
Theorem 8.22(b) (Zeng–Cao–Dai–Wang–Liao, *Sparse Discrepancy Beyond Additive Functions*, STOC 2027
submission manuscript (sha256 0f09ec60…25b81), p.38). -/
def NoTwoNeighboursOnAvoidingCycle {V : Type} (G : SimpleGraph V) : Prop :=
∀ v a b, a ≠ b → G.Adj v a → G.Adj v b →
¬ ∃ p : G.Walk a a, p.IsCycle ∧ b ∈ p.support ∧ v ∉ p.support
end SparseDisc.Supplement
Source
Zeng–Cao–Dai–Wang–Liao, Sparse Discrepancy Beyond Additive Functions, STOC 2027 submission (manuscript sha256 0f09ec60…), Theorem 8.22(b), p.38