simple_graph_unique_path_of_weight_lt_half_girth
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.
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.
by_contra hne obtain ⟨a, b, p', q', hp', hq', hc⟩ := hp₁.exists_isCycle_of_ne hp₂ hne let c := p'.append q'.reverse
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.
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))
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.
uses
List.mem_appendhave 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))
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₂.
uses
List.Sublist.sum_le_sum,List.mem_map,List.map_append,List.sum_append,List.map_reverse,List.sum_reversehave 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
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.
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
- Linear arithmetic (`linarith` on line 34) automatically derives the contradiction gw < gw from the accumulated inequalities.
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.
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