AFTD Auto-Formalizing Theoretical Domains

edge_geodesic_transversal_bound_of_edge_cut

theoremverifiedformalization

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|.

  1. 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.

    lines 7–12

      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
  2. 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.

    lines 13–18

        · 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⟩
  3. 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|.

    lines 19–21

    uses Nat.sInf_le

      dsimp [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.

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

/-- 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⟩
See it in the graphDiscuss this resultChallenge it