AFTD Auto-Formalizing Theoretical Domains

edge_cut_transversal_theorem

theoremverifiedformalization

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.

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

    lines 11–22

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

    lines 23–26

    uses Nat.sInf_le

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

    lines 27–33

    uses le_csInf

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

    lines 34–43

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

    lines 44–54

    uses Finset.card_le_card_of_injOn

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

    line 55

    uses le_antisymm

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

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

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