AFTD Auto-Formalizing Theoretical Domains

simple_graph_odd_girth_ge

def

A simple graph G has odd girth at least k if every cycle in G of odd length has length at least k.

Statement

def simple_graph_odd_girth_ge {V : Type*} (G : SimpleGraph V) (k : ℕ) : Prop
Defined in
arXiv:2611.05178 Question 5.5
Verified
04 Nov 2026
Axioms
none listed
Used by 1

Read back from the Lean

For a type V, a simple graph G on V, and a natural number k, simple_graph_odd_girth_ge G k asserts that every cycle in G of odd length has length at least k; that is, for every vertex u : V and every closed walk w from u to u in G, if w is a cycle (w.IsCycle) and w.length is odd, then k ≤ w.length.

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 G has odd girth at least k if every cycle of odd length has length at least k. -/
def simple_graph_odd_girth_ge {V : Type*} (G : SimpleGraph V) (k : ℕ) : Prop := ∀ (u : V) (w : G.Walk u u), w.IsCycle → Odd w.length → k ≤ w.length
See it in the graphDiscuss this resultChallenge it