AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_cactus

def

A simple graph is a cactus if any two simple cycles that share an edge have identical edge sets (every edge belongs to at most one simple cycle).

Statement

def simple_graph_is_cactus {V : Type*} (G : SimpleGraph V) : Prop
Defined in
arXiv:2610.11717 Sec. 2
Verified
19 Oct 2026
Axioms
none listed
Used by 4

Read back from the Lean

For a type V and a simple graph G on V, simple_graph_is_cactus G asserts that for all vertices u₁, u₂ : V, and all closed walks p₁ : G.Walk u₁ u₁ and p₂ : G.Walk u₂ u₂, if p₁ is a cycle (p₁.IsCycle) and p₂ is a cycle (p₂.IsCycle), and there exists an edge e that belongs to both the edge list of p₁ and the edge list of p₂, then the subgraph traced by p₁ equals the subgraph traced by p₂ (p₁.toSubgraph = p₂.toSubgraph).

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 is a cactus if every edge belongs to at most one simple cycle. -/
def simple_graph_is_cactus {V : Type*} (G : SimpleGraph V) : Prop := ∀ ⦃u₁ u₂ : V⦄ (p₁ : G.Walk u₁ u₁) (p₂ : G.Walk u₂ u₂),
    p₁.IsCycle → p₂.IsCycle →
    (∃ e, e ∈ p₁.edges ∧ e ∈ p₂.edges) →
    p₁.toSubgraph = p₂.toSubgraph
See it in the graphDiscuss this resultChallenge it