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
- is_bipartite_cactus_nfaAn NFA A is a bipartite cactus automaton if its undirected transition graph is a cactus and 2-colorable.
- strongly_cactus_nfaAn NFA A is a strongly cactus automaton of parity p with initial state s when: s is the only start state and no transition enters s; the…
- min_bipartite_cactus_nfa_states_emptyThe empty language over any alphabet has a bipartite cactus NFA with at most one state.
- empty_graph_is_cactusThe edgeless graph on any vertex type is a cactus graph.
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