empty_graph_is_cactus
The edgeless graph on any vertex type is a cactus graph.
Statement
theorem empty_graph_is_cactus (V : Type*) : simple_graph_is_cactus (⊥ : SimpleGraph V)
- Source
- folklore
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- simple_graph_is_cactusA 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…
Read back from the Lean
For any type V, the empty simple graph on V (the graph with no edges, ⊥ : SimpleGraph V) is a cactus graph: for all vertices u₁, u₂ : V and any closed walks p₁ from u₁ to u₁ and p₂ from u₂ to u₂ in ⊥, if p₁ and p₂ are cycles and they share an edge (there exists an edge e in both p₁.edges and p₂.edges), then their induced subgraphs p₁.toSubgraph and p₂.toSubgraph are equal.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To show that the edgeless graph $\bot$ is a cactus graph, we unpack the definition: any two cycles sharing an edge must induce the same subgraph. We assume for contradiction that there exist two cycles $p_1$ and $p_2$ sharing an edge $e$. A case split on the walk $p_1$ shows that $p_1$ cannot be trivial (as it contains an edge $e$) and cannot be non-trivial (as the empty graph has no edges). Both cases are immediately contradictory, so the cactus condition holds vacuously.
To show that the empty graph is a cactus, it suffices to assume that two cycles share an edge and derive a contradiction.
Unfolding the definition of `simple_graph_is_cactus`, the condition requires that any two cycles sharing an edge define the same subgraph. We introduce two cycles $p_1$ (from $u_1$ to $u_1$) and $p_2$ (from $u_2$ to $u_2$), their cycle proofs $hp_1$ and $hp_2$, and the assumption $h$ that there exists an edge $e$ shared by both $p_1$ and $p_2$.
unfold simple_graph_is_cactus intro u₁ u₂ p₁ p₂ hp₁ hp₂ h
The walk $p_1$ cannot exist, completing the proof by contradiction.
We case split on the construction of the walk $p_1$: - If $p_1$ is the trivial walk `nil`, its edge list is empty, which contradicts the hypothesis $h$ that $e$ is an edge of $p_1$. The tactic `simp at h` recognizes this contradiction and closes the branch. - If $p_1$ is of the form `cons hadj p`, it requires an adjacency `hadj : ⊥.Adj u₁ v` in the graph. But the empty graph $\bot$ has no edges, so `simp at hadj` recognizes that $\bot\text{.Adj}$ is empty and closes this branch. Both cases are impossible, so the claim holds vacuously.
cases p₁ with | nil => simp at h | cons hadj p => simp at hadj
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The empty graph on any vertex type is a cactus graph. -/theorem empty_graph_is_cactus (V : Type*) : simple_graph_is_cactus (⊥ : SimpleGraph V) := by unfold simple_graph_is_cactus intro u₁ u₂ p₁ p₂ hp₁ hp₂ h cases p₁ with | nil => simp at h | cons hadj p => simp at hadj