Widest path: equality with the minimum maximum-edge cut
ProvedQAlgorithms.Papers.Independent.Support50.P47.widest_path_cut_propertyLet be a finite connected undirected graph with distinct vertices , and let assign an arbitrary real weight to every edge. Parallel edges, if present, retain distinct labels. Let contain all simple paths from to . For a vertex set containing but not , let be the set of edges with exactly one endpoint in . Define a path's weight as its minimum edge weight and a cut's weight as its maximum crossing-edge weight. Then
Both extrema are attained. Every path and separating cut has a nonempty finite edge set. Negative weights are allowed. This identifies the bottleneck routing value with a cut obstruction, without quantum-channel assumptions.
Formalization Note The Lean conclusion supplies an optimizing path and cut, equality of their weights, and the universal optimality inequalities. Edge orientation in the data only chooses endpoint names; traversals and cut membership are undirected.
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P47
namespace QAlgorithms.Papers.Independent.Support50.P47
noncomputable section
universe u v
/-- PDF pp.23–24, Proposition 12, Eq.(131): the widest simple endpoint route
and a minimum endpoint cut exist and have the same weight. Weights are arbitrary
reals, including negative ones; parallel labelled edges are retained.
The universal clauses state both extrema with attainment, avoiding totalized
suprema over empty or unbounded collections. No quantum hypothesis is imposed. -/
theorem widest_path_cut_property {V : Type u} {E : Type v}
[Fintype V] [Fintype E] (G : WeightedNetwork V E)
(hconn : IsConnected G) (a b : V) (hab : a ≠ b) :
∃ p : Route G a b, ∃ A : Set V,
a ∈ A ∧ b ∉ A ∧ routeWeight G p = cutWeight G A ∧
(∀ q : Route G a b, routeWeight G q ≤ routeWeight G p) ∧
(∀ B : Set V, a ∈ B → b ∉ B → cutWeight G A ≤ cutWeight G B) := by sorry
end
end QAlgorithms.Papers.Independent.Support50.P47
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For every pair of finite types , every network with endpoint functions satisfying for every edge and arbitrary real weights , assume that every two distinct vertices are joined by a route. Here a route from to means a sequence of pairwise distinct vertices , with , , and , together with edges joining each successive pair in either endpoint order. For every satisfying , there exist a route from to and a set such that
Here is the infimum, equivalently the minimum, of the finite nonempty set of weights of the edges occurring in route ; is the supremum of the weights of all edges having exactly one endpoint in , equivalently their maximum when such edges exist and when none exist; and ranges over all routes just described. The existence assertion requires neither nor to be unique. Although empty and singleton finite vertex types are included in the universal quantification, they admit no choice of satisfying .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.