AFTD Auto-Formalizing Theoretical Domains

simple_graph_unique_path_of_weight_lt_half_girth

theoremverified

Let G be a simple graph, let ω : Sym2 V → ℝ be a nonnegative edge weight function (0 ≤ ω e for all e ∈ G.edgeSet), and let gw > 0. If every cycle in G has total edge weight at least gw, then between any two vertices u and v in G, there is at most one path of total edge weight strictly less than gw / 2.

Statement

open scoped BigOperators in
open Classical in
theorem simple_graph_unique_path_of_weight_lt_half_girth {V : Type*}
    (G : SimpleGraph V) (ω : Sym2 V → ℝ) (hω : ∀ e ∈ G.edgeSet, 0 ≤ ω e)
    (gw : ℝ) (hgw : 0 < gw)
    (hgirth : ∀ (u : V) (p : G.Walk u u), p.IsCycle → gw ≤ (p.edges.map ω).sum)
    {u v : V} (p₁ p₂ : G.Walk u v) (hp₁ : p₁.IsPath) (hp₂ : p₂.IsPath)
    (hw₁ : (p₁.edges.map ω).sum < gw / 2)
    (hw₂ : (p₂.edges.map ω).sum < gw / 2) :
    p₁ = p₂
Source
arXiv:2611.15755 Appendix B, Lemma B.1 -- Asymptotically Optimal Bounds for Counting Near-Minimum Circuits in Regular Matroids
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

Read back from the Lean

For any type V, let G be a simple graph on V, and let ω : Sym2 V → ℝ be a function assigning real weights to unordered pairs of vertices such that ω e ≥ 0 for every edge e ∈ G.edgeSet. Let gw be a strictly positive real number (0 < gw) such that every cycle in G has total edge weight at least gw (i.e., for every vertex w : V and every closed walk p : G.Walk w w, if p.IsCycle then the sum of ω over the edges of p is at least gw). Then, for any two vertices u, v : V, and any two paths p₁, p₂ : G.Walk u v (meaning p₁.IsPath and p₂.IsPath), if the total weight of the edges of p₁ is strictly less than gw / 2 and the total weight of the edges of p₂ is strictly less than gw / 2, then p₁ = p₂.

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

We argue by contradiction: if there were two distinct paths p₁ and p₂ between u and v, they would contain subwalks whose concatenation forms a cycle c. Because the edges of c form a sublist of the edges of p₁ together with the reversed edges of p₂, and all edge weights are nonnegative, the total weight of c is bounded by the sum of the weights of p₁ and p₂. Each path has weight strictly less than gw / 2, so the cycle would have weight strictly less than gw, contradicting the assumption that every cycle has weight at least gw.

  1. Assuming for contradiction that p₁ ≠ p₂, there exists a cycle c formed by a subwalk p' of p₁ and the reversal of a subwalk q' of p₂.

    We assume for contradiction that the two paths p₁ and p₂ are not equal (`by_contra hne`). By a standard property of simple graphs, two distinct paths sharing endpoints must contain subwalks p' and q' between two vertices a and b such that appending p' to the reversal of q' forms a cycle c.

    lines 12–14

      by_contra hne
      obtain ⟨a, b, p', q', hp', hq', hc⟩ := hp₁.exists_isCycle_of_ne hp₂ hne
      let c := p'.append q'.reverse
  2. The edge list of the cycle c is a sublist of the concatenation of the edges of p₁ and the reversed edges of p₂.

    The edges of c consist of the edges of p' followed by the reversed edges of q' (lines 15–16). Because p' is a subwalk of p₁ and q' is a subwalk of p₂, their edge lists are infixes (hence sublists) of the edge lists of p₁ and p₂, respectively; combining them shows that c.edges is a sublist of p₁.edges ++ p₂.edges.reverse.

    lines 15–19

      have hcedges : c.edges = p'.edges ++ q'.edges.reverse := by
        simp [c]
      have hsub : c.edges.Sublist (p₁.edges ++ p₂.edges.reverse) := by
        rw [hcedges]
        exact (hp'.edges_isInfix.sublist.append (hq'.edges_isInfix.sublist.reverse))
  3. Every edge in p₁.edges ++ p₂.edges.reverse has nonnegative weight under ω.

    Any edge e in the concatenated list belongs either to p₁.edges or to p₂.edges.reverse (by `List.mem_append`). In either case e is an edge of the graph G, so the hypothesis hω guarantees that 0 ≤ ω e.

    lines 20–25

    uses List.mem_append

      have hnonneg : ∀ e ∈ p₁.edges ++ p₂.edges.reverse, 0 ≤ ω e := by
        intro e he
        rw [List.mem_append] at he
        rcases he with he | he
        · exact hω e (p₁.edges_subset_edgeSet he)
        · exact hω e (p₂.edges_subset_edgeSet (by simpa using he))
  4. The total edge weight of the cycle c is at most the sum of the total edge weights of p₁ and p₂.

    Because c.edges is a sublist of p₁.edges ++ p₂.edges.reverse and all edge weights are nonnegative, `List.Sublist.sum_le_sum` (along with `List.mem_map`) implies that the weight of c is at most the sum of the weights along p₁.edges ++ p₂.edges.reverse. Distributing the map and sum operations over concatenation and reversal (`List.map_append`, `List.sum_append`, `List.map_reverse`, `List.sum_reverse`) evaluates this upper bound to the sum of the weights of p₁ and p₂.

    lines 26–32

    uses List.Sublist.sum_le_sum, List.mem_map, List.map_append, List.sum_append, List.map_reverse, List.sum_reverse

      have hsumle : (c.edges.map ω).sum ≤ (p₁.edges.map ω).sum + (p₂.edges.map ω).sum := by
        have hs := List.Sublist.sum_le_sum (hsub.map ω) (by
          intro a ha
          rw [List.mem_map] at ha
          obtain ⟨e, he, rfl⟩ := ha
          exact hnonneg e he)
        simpa [List.map_append, List.sum_append, List.map_reverse, List.sum_reverse] using hs
  5. A contradiction is reached, proving that p₁ = p₂. automation

    By the girth hypothesis applied to c, the weight of c is at least gw (line 33). But the previous step established that the weight of c is at most weight(p₁) + weight(p₂), where each path has weight strictly less than gw / 2. Linear arithmetic (`linarith`) finds the resulting inequality gw < gw / 2 + gw / 2 = gw impossible, closing the proof.

    lines 33–34

      have hgwle : gw ≤ (c.edges.map ω).sum := hgirth a c hc
      linarith
List.mem_append
an element belongs to the concatenation of two lists if and only if it belongs to the first list or the second list
List.Sublist.sum_le_sum
if one list is a sublist of another and all elements of the second list are nonnegative, then the sum of the elements in the first list is at most the sum of the elements in the second list
List.mem_map
an element belongs to the image of a list under a function if and only if it is the image of some element in the original list
List.map_append
mapping a function over the concatenation of two lists equals the concatenation of the mapped lists
List.sum_append
the sum of the concatenation of two lists is the sum of their individual sums
List.map_reverse
mapping a function over the reversal of a list equals the reversal of the mapped list
List.sum_reverse
the sum of elements in the reversal of a list equals the sum of the original list

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

open scoped BigOperators inopen Classical in/-- Between any two vertices, there is at most one path of weight strictly less than half the weighted girth in a nonnegative-weighted graph. -/theorem simple_graph_unique_path_of_weight_lt_half_girth {V : Type*}    (G : SimpleGraph V) (ω : Sym2 V → ℝ) (hω : ∀ e ∈ G.edgeSet, 0 ≤ ω e)    (gw : ℝ) (hgw : 0 < gw)    (hgirth : ∀ (u : V) (p : G.Walk u u), p.IsCycle → gw ≤ (p.edges.map ω).sum)    {u v : V} (p₁ p₂ : G.Walk u v) (hp₁ : p₁.IsPath) (hp₂ : p₂.IsPath)    (hw₁ : (p₁.edges.map ω).sum < gw / 2)    (hw₂ : (p₂.edges.map ω).sum < gw / 2) :    p₁ = p₂ := by  by_contra hne  obtain ⟨a, b, p', q', hp', hq', hc⟩ := hp₁.exists_isCycle_of_ne hp₂ hne  let c := p'.append q'.reverse  have hcedges : c.edges = p'.edges ++ q'.edges.reverse := by    simp [c]  have hsub : c.edges.Sublist (p₁.edges ++ p₂.edges.reverse) := by    rw [hcedges]    exact (hp'.edges_isInfix.sublist.append (hq'.edges_isInfix.sublist.reverse))  have hnonneg : ∀ e ∈ p₁.edges ++ p₂.edges.reverse, 0 ≤ ω e := by    intro e he    rw [List.mem_append] at he    rcases he with he | he    · exact hω e (p₁.edges_subset_edgeSet he)    · exact hω e (p₂.edges_subset_edgeSet (by simpa using he))  have hsumle : (c.edges.map ω).sum ≤ (p₁.edges.map ω).sum + (p₂.edges.map ω).sum := by    have hs := List.Sublist.sum_le_sum (hsub.map ω) (by      intro a ha      rw [List.mem_map] at ha      obtain ⟨e, he, rfl⟩ := ha      exact hnonneg e he)    simpa [List.map_append, List.sum_append, List.map_reverse, List.sum_reverse] using hs  have hgwle : gw ≤ (c.edges.map ω).sum := hgirth a c hc  linarith
See it in the graphDiscuss this resultChallenge it