edge_cut_transversal_theorem
Let G be a connected simple graph. Let S be a finite set of edges of G of cardinality k that is an edge cut induced by a vertex subset X (meaning there exists X : Set V such that for all e, e ∈ S ↔ e ∈ G.edgeSet ∧ ∃ u ∈ X, ∃ v ∉ X, e = s(u, v)), such that the number of connected components of G after deleting the edges in S is 2 (Nat.card of the connected components of G.deleteEdges S is 2). If for all vertices u, v and every walk p from u to v in G such that is_maximal_geodesic p, there exists a unique edge e such that e ∈ S ∧ e ∈ p.edges, and G contains k mutually edge-disjoint maximal geodesics (meaning there exist endpoints u, v : Fin k → V and walks P : (i : Fin k) → G.Walk (u i) (v i) such that each P i is a maximal geodesic and for all i ≠ j, any edge in P i does not belong to P j), then the edge geodesic transversal number of G equals the cardinality of S.
Statement
theorem edge_cut_transversal_theorem {V : Type*} (G : SimpleGraph V) (hG : G.Connected) (S : Finset (Sym2 V)) (k : ℕ) (hk : S.card = k) (hcut : ∃ X : Set V, ∀ e, e ∈ S ↔ e ∈ G.edgeSet ∧ ∃ u ∈ X, ∃ v ∉ X, e = s(u, v)) (_hconn : Nat.card (G.deleteEdges (S : Set (Sym2 V))).ConnectedComponent = 2) (h_inter : ∀ ⦃u v : V⦄ (p : G.Walk u v), is_maximal_geodesic p → ∃! e, e ∈ S ∧ e ∈ p.edges) (h_disj : ∃ (u v : Fin k → V) (P : (i : Fin k) → G.Walk (u i) (v i)), (∀ i, is_maximal_geodesic (P i)) ∧ ∀ (i j : Fin k), i ≠ j → ∀ e ∈ (P i).edges, e ∉ (P j).edges) : edge_geodesic_transversal_number G = S.card
- Formalizes
- arXiv:2610.36821 Theorem 5
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- is_maximal_geodesicA geodesic p from u to v is maximal if no adjacent vertex at either endpoint extends it to a strictly longer geodesic.
- edge_geodesic_transversal_numberThe edge geodesic transversal number of a simple graph G is the infimum in ℕ of the set of natural numbers k such that there exists a…
- is_edge_geodesic_transversalA finite set S of edges of G is an edge geodesic transversal if every maximal geodesic in G contains at least one edge of S.
Read back from the Lean
Let $V$ be a type, and let $G$ be a simple graph on $V$. Assume:
1. $G$ is connected (hG).
2. $S$ is a finite set of unordered pairs of vertices in $V$ (S : Finset (Sym2 V)).
3. $k$ is a natural number such that $|S| = k$ (hk).
4. $S$ is an edge cut of $G$: there exists a vertex subset $X \subseteq V$ such that an unordered pair $e$ is in $S$ if and only if $e$ is an edge of $G$ and there exist $u \in X$ and $v \notin X$ with $e = s(u, v)$ (hcut).
5. The subgraph obtained by removing the edges in $S$ from $G$ has exactly 2 connected components (_hconn).
6. Every maximal geodesic walk in $G$ contains exactly one edge from $S$ (h_inter).
7. There exist $k$ pairwise edge-disjoint maximal geodesic walks in $G$: that is, there exist vertex assignments $u, v : \mathrm{Fin}\, k \to V$ and walks $P_i$ from $u(i)$ to $v(i)$ for each $i \in \mathrm{Fin}\, k$ such that each $P_i$ is a maximal geodesic, and for all $i \ne j$, no edge of $P_i$ is an edge of $P_j$ (h_disj).
Then the edge geodesic transversal number of $G$ equals $|S|$ (which is $k$).
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
The edge geodesic transversal number of G is the minimum size of an edge set that intersects every maximal geodesic in G. The proof shows this number equals |S| by proving two inequalities. For the upper bound, the hypothesis that every maximal geodesic intersects S ensures S is a valid transversal, so the transversal number is at most |S|. For the lower bound, the existence of k = |S| pairwise edge-disjoint maximal geodesics means any transversal T must contain an edge from each, yielding an injection from a k-element set into T and thus forcing |T| ≥ k.
S is an edge geodesic transversal of G.
By definition, an edge geodesic transversal must consist of edges of G and must intersect every maximal geodesic walk in G. First, the cut hypothesis `hcut` implies every edge e ∈ S is an edge of G. Second, for any maximal geodesic walk p, the intersection hypothesis `h_inter` provides an edge e ∈ S that belongs to the edges of p. Thus S satisfies both defining conditions of an edge geodesic transversal.
have _ := hG have hS_trans : is_edge_geodesic_transversal G S := by constructor · intro e he rcases hcut with ⟨X, hX⟩ exact ((hX e).mp he).1 · intro u v p hp have hp_max : is_maximal_geodesic p := by dsimp [is_maximal_geodesic] tauto rcases h_inter p hp_max with ⟨e, ⟨heS, he_p⟩, _⟩ exact ⟨e, heS, he_p⟩
The edge geodesic transversal number of G is at most |S|.
The edge geodesic transversal number of G is defined as the infimum of the cardinalities of all finite edge geodesic transversals. Since S is an edge geodesic transversal, its cardinality |S| belongs to the set over which the infimum is taken. By `Nat.sInf_le`, the infimum is at most |S|.
uses
Nat.sInf_lehave h_le : edge_geodesic_transversal_number G ≤ S.card := by dsimp [edge_geodesic_transversal_number] apply Nat.sInf_le exact ⟨S, hS_trans, rfl⟩
To show |S| ≤ edge_geodesic_transversal_number G, it suffices to show that any edge geodesic transversal T satisfies k ≤ |T|.
Since |S| = k, this is the claim that k is a lower bound for the infimum. By `le_csInf`, it suffices to check that the set of transversal sizes is nonempty (witnessed by S) and that k ≤ |T| for every edge geodesic transversal T. The hypothesis `h_disj` is then destructured to obtain k maximal geodesics P 0, ..., P (k - 1) that are pairwise edge-disjoint.
uses
le_csInfhave h_ge : S.card ≤ edge_geodesic_transversal_number G := by rw [hk] dsimp [edge_geodesic_transversal_number] apply le_csInf · exact ⟨S.card, ⟨S, hS_trans, rfl⟩⟩ · rintro b ⟨T, hT, rfl⟩ rcases h_disj with ⟨u, v, P, hP_max, hP_disj⟩
There exists a function f : Fin k → Sym2 V selecting an edge in T from each of the k maximal geodesics.
For each index i, P i is a maximal geodesic. Since T is an edge geodesic transversal, T must contain at least one edge of P i. Applying the axiom of choice (`choose`), we obtain a choice function f such that for each i, f i ∈ T and f i is an edge of P i.
have h_exists_e : ∀ i : Fin k, ∃ e ∈ T, e ∈ (P i).edges := by intro i have hp_geom : (P i).IsPath ∧ (P i).length = G.dist (u i) (v i) ∧ (∀ w, G.Adj w (u i) → G.dist w (v i) ≤ (P i).length) ∧ (∀ w, G.Adj (v i) w → G.dist (u i) w ≤ (P i).length) := by have := hP_max i dsimp [is_maximal_geodesic] at this tauto exact hT.2 (P i) hp_geom choose f hfT hfP using h_exists_e
The cardinality of T is at least k.
The function f maps the k-element universe {0, ..., k - 1} into T. If f i = f j for distinct indices i ≠ j, then the edge f i would belong to both P i and P j, contradicting the pairwise edge-disjointness of the geodesics. Hence f is injective on {0, ..., k - 1}. By `Finset.card_le_card_of_injOn`, the size of the domain, k, is at most |T|.
uses
Finset.card_le_card_of_injOnhave h_inj : Set.InjOn f (Finset.univ : Finset (Fin k)) := by intros i _ j _ hij by_contra hne have := hP_disj i j hne (f i) (hfP i) rw [hij] at this exact this (hfP j) have h_maps : Set.MapsTo f (Finset.univ : Finset (Fin k)) T := by intros i _ exact hfT i have h_card := Finset.card_le_card_of_injOn f h_maps h_inj simpa using h_card
The edge geodesic transversal number of G equals |S|.
Combining the upper bound edge_geodesic_transversal_number G ≤ |S| and the lower bound |S| ≤ edge_geodesic_transversal_number G via `le_antisymm` yields the equality.
uses
le_antisymmexact le_antisymm h_le h_ge
Nat.sInf_le- If a natural number belongs to a set of natural numbers, the infimum of the set is at most that number.
le_csInf- A value is less than or equal to the infimum of a nonempty set if it is a lower bound for every element of the set.
Finset.card_le_card_of_injOn- If a function maps a finite set s into a finite set t and is injective on s, then the cardinality of s is at most the cardinality of t.
le_antisymm- In a partial order, if a ≤ b and b ≤ a, then a = b.
- The theorem statement assumes that G is connected (`hG`) and that deleting the edge cut S leaves exactly two connected components (`_hconn`), matching Theorem 5 of arXiv:2610.36821. However, neither assumption is used in the formal proof.
- The intersection hypothesis `h_inter` assumes that every maximal geodesic intersects S in a unique edge, but the upper bound only requires the existence of at least one intersecting edge.
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.
/-- Theorem 5 (Edge-cut transversal theorem) of arXiv:2610.36821. -/theorem edge_cut_transversal_theorem {V : Type*} (G : SimpleGraph V) (hG : G.Connected) (S : Finset (Sym2 V)) (k : ℕ) (hk : S.card = k) (hcut : ∃ X : Set V, ∀ e, e ∈ S ↔ e ∈ G.edgeSet ∧ ∃ u ∈ X, ∃ v ∉ X, e = s(u, v)) (_hconn : Nat.card (G.deleteEdges (S : Set (Sym2 V))).ConnectedComponent = 2) (h_inter : ∀ ⦃u v : V⦄ (p : G.Walk u v), is_maximal_geodesic p → ∃! e, e ∈ S ∧ e ∈ p.edges) (h_disj : ∃ (u v : Fin k → V) (P : (i : Fin k) → G.Walk (u i) (v i)), (∀ i, is_maximal_geodesic (P i)) ∧ ∀ (i j : Fin k), i ≠ j → ∀ e ∈ (P i).edges, e ∉ (P j).edges) : edge_geodesic_transversal_number G = S.card := by have _ := hG have hS_trans : is_edge_geodesic_transversal G S := by constructor · intro e he rcases hcut with ⟨X, hX⟩ exact ((hX e).mp he).1 · intro u v p hp have hp_max : is_maximal_geodesic p := by dsimp [is_maximal_geodesic] tauto rcases h_inter p hp_max with ⟨e, ⟨heS, he_p⟩, _⟩ exact ⟨e, heS, he_p⟩ have h_le : edge_geodesic_transversal_number G ≤ S.card := by dsimp [edge_geodesic_transversal_number] apply Nat.sInf_le exact ⟨S, hS_trans, rfl⟩ have h_ge : S.card ≤ edge_geodesic_transversal_number G := by rw [hk] dsimp [edge_geodesic_transversal_number] apply le_csInf · exact ⟨S.card, ⟨S, hS_trans, rfl⟩⟩ · rintro b ⟨T, hT, rfl⟩ rcases h_disj with ⟨u, v, P, hP_max, hP_disj⟩ have h_exists_e : ∀ i : Fin k, ∃ e ∈ T, e ∈ (P i).edges := by intro i have hp_geom : (P i).IsPath ∧ (P i).length = G.dist (u i) (v i) ∧ (∀ w, G.Adj w (u i) → G.dist w (v i) ≤ (P i).length) ∧ (∀ w, G.Adj (v i) w → G.dist (u i) w ≤ (P i).length) := by have := hP_max i dsimp [is_maximal_geodesic] at this tauto exact hT.2 (P i) hp_geom choose f hfT hfP using h_exists_e have h_inj : Set.InjOn f (Finset.univ : Finset (Fin k)) := by intros i _ j _ hij by_contra hne have := hP_disj i j hne (f i) (hfP i) rw [hij] at this exact this (hfP j) have h_maps : Set.MapsTo f (Finset.univ : Finset (Fin k)) T := by intros i _ exact hfT i have h_card := Finset.card_le_card_of_injOn f h_maps h_inj simpa using h_card exact le_antisymm h_le h_ge