edge_geodesic_transversal_bound_of_edge_cut
Let G be a connected simple graph. Let S be a finite set of edges of G 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)). 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, then the edge geodesic transversal number of G is at most the cardinality of S.
Statement
theorem edge_geodesic_transversal_bound_of_edge_cut {V : Type*} (G : SimpleGraph V) (hG : G.Connected) (S : Finset (Sym2 V)) (hcut : ∃ X : Set V, ∀ e, e ∈ S ↔ e ∈ G.edgeSet ∧ ∃ u ∈ X, ∃ v ∉ X, e = s(u, v)) (h_inter : ∀ ⦃u v : V⦄ (p : G.Walk u v), is_maximal_geodesic p → ∃! e, e ∈ S ∧ e ∈ p.edges) : edge_geodesic_transversal_number G ≤ S.card
- Formalizes
- arXiv:2610.36821 Lemma 3
- 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 G is connected (hG). Let S be a finite set of unordered pairs of vertices of V. Assume there exists a subset X ⊆ V such that an unordered pair e is in S if and only if e is an edge of G and there exist u ∈ X and v ∉ X such that e = s(u, v) (hcut). Assume further that for all vertices u, v : V and every walk p from u to v in G, if p is a maximal geodesic (meaning p is a path, the length of p equals the graph distance G.dist u v, every neighbor w of u satisfies G.dist w v ≤ p.length, and every neighbor w of v satisfies G.dist u w ≤ p.length), then there exists a unique edge e such that e ∈ S and e is an edge of p (h_inter). Then the edge geodesic transversal number of G is less than or equal to the cardinality of S.
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 prove that the edge geodesic transversal number of G is at most |S|, the proof establishes that S is itself an edge geodesic transversal of G. First, every edge in S belongs to G because S is an edge cut. Second, S intersects every maximal geodesic in G because, by hypothesis, every maximal geodesic intersects S in a unique edge. Since the edge geodesic transversal number is defined as the infimum of the cardinalities of all edge geodesic transversals, the existence of S as a transversal immediately bounds the transversal number by |S|.
Every element of S is an edge of the graph G.
To show that S is an edge geodesic transversal of G, we first prove that every e ∈ S belongs to the edge set of G. This follows directly from the assumption that S is an edge cut induced by a vertex set X: by definition, any e ∈ S is an edge of G connecting X to its complement.
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
S intersects every maximal geodesic, establishing that S is an edge geodesic transversal of G.
For the second condition of an edge geodesic transversal, let p be any walk from u to v satisfying the maximality and geodesic conditions. Unfolding the definition of is_maximal_geodesic shows that p is precisely a maximal geodesic. By hypothesis h_inter, there exists a unique edge e in both S and the edges of p. Taking this edge e demonstrates that S meets p, which completes the proof that S is an edge geodesic transversal.
· 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|.
By definition, the edge geodesic transversal number of G is the infimum of the sizes of all edge geodesic transversals of G. Since S is an edge geodesic transversal, its cardinality |S| belongs to this set of sizes. By Nat.sInf_le, the infimum is at most |S|.
uses
Nat.sInf_ledsimp [edge_geodesic_transversal_number] apply Nat.sInf_le exact ⟨S, hS_trans, rfl⟩
Nat.sInf_le- For any set of natural numbers s and any element m ∈ s, the infimum sInf s is at most m.
- The connectedness hypothesis `hG` is recorded in line 7 but never used in the proof.
- The hypothesis `h_inter` assumes that every maximal geodesic intersects `S` in a unique edge (`∃! e`), but establishing that `S` is an edge geodesic transversal only requires at least one edge (`∃ e`), so the uniqueness is unused.
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.
/-- Lemma 3 of arXiv:2610.36821: An edge cut intersecting every maximal geodesic uniquely gives an upper bound on gt_e(G). -/theorem edge_geodesic_transversal_bound_of_edge_cut {V : Type*} (G : SimpleGraph V) (hG : G.Connected) (S : Finset (Sym2 V)) (hcut : ∃ X : Set V, ∀ e, e ∈ S ↔ e ∈ G.edgeSet ∧ ∃ u ∈ X, ∃ v ∉ X, e = s(u, v)) (h_inter : ∀ ⦃u v : V⦄ (p : G.Walk u v), is_maximal_geodesic p → ∃! e, e ∈ S ∧ e ∈ p.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⟩ dsimp [edge_geodesic_transversal_number] apply Nat.sInf_le exact ⟨S, hS_trans, rfl⟩