flow_supports_rate_zero
On any capacitated network net with unicast sessions sess, the common rate zero is always supported by fractional multicommodity flow.
Statement
theorem flow_supports_rate_zero {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K] (net : CapacitatedNetwork V) (sess : UnicastSessions V K) : FlowSupportsRate net sess 0
- Source
- folklore
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- CapacitatedNetworkAn undirected capacitated network on a finite vertex set V given by a simple graph G where each edge in G has strictly positive capacity…
- UnicastSessionsA collection of unicast communication sessions indexed by a type K on an arbitrary vertex type V, consisting of a source map src : K → V,…
- FlowSupportsRateA common rate r is supported by fractional multicommodity flow on a capacitated network net with unicast sessions sess if there exists a…
- IsMulticommodityFlowGiven a capacitated network on a finite vertex type V with decidable equality, and unicast sessions indexed by a finite type K with…
- Used by 1
- flow_supports_rate_monoIf a fractional multicommodity flow on net with sessions sess supports common rate r, then for any non-negative rate r' ≤ r, rate r' is…
Read back from the Lean
For any finite types V and K with decidable equality, any capacitated network net on V, and any unicast sessions sess indexed by K, the network net supports a transmission rate of 0 for the sessions sess (that is, FlowSupportsRate net sess 0).
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
Any capacitated network supports a common rate of zero for all unicast sessions. The proof explicitly exhibits the zero flow, which assigns zero flow to every commodity and vertex pair. Non-negativity and flow conservation hold trivially because both the flow values and the required rate are zero, while the capacity constraints hold because network capacities are always non-negative (strictly positive on graph edges and zero otherwise).
It suffices to verify that the identically zero flow satisfies the three defining conditions of a multicommodity flow at rate 0.
By definition, a rate is supported if there exists a multicommodity flow achieving it. Choosing the zero flow f(k, u, v) = 0 for all commodities k and vertices u, v reduces the goal to three requirements: non-negativity, capacity constraints, and flow conservation.
refine ⟨fun _ _ _ => 0, ?_, ?_, ?_⟩
The zero flow is non-negative everywhere.
For any commodity k and pair of vertices u and v, the flow value is 0, and the inequality 0 ≤ 0 holds trivially.
· intro k u v; simp
The zero flow satisfies the capacity constraint on every pair of distinct vertices.
For any distinct vertices u and v, the total flow between them in both directions is 0 + 0 = 0. To show that this is at most net.cap s(u, v), we distinguish whether s(u, v) is an edge of the network: if it is, its capacity is strictly positive, hence non-negative by le_of_lt; if it is not, its capacity is 0 by definition. The total zero flow is therefore at most the capacity.
uses
le_of_lt· intro u v huv have hcap : 0 ≤ net.cap s(u, v) := by by_cases h : s(u, v) ∈ net.G.edgeSet · exact le_of_lt (net.cap_pos _ h) · rw [net.cap_zero _ h] simpa using hcap
The zero flow satisfies flow conservation at every vertex for every commodity.
For each commodity k and vertex v, the net flow out of v is 0 - 0 = 0. The demand on the right-hand side is 0 at the source vertex, -0 = 0 at the target vertex, and 0 at intermediate vertices. Both sides simplify to 0, satisfying flow conservation.
· intro k v simp
le_of_lt- In any preorder, a strictly smaller element is also less than or equal: if a < b 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
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.
/-- The zero common rate is always supported by fractional multicommodity flow. -/theorem flow_supports_rate_zero {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K] (net : CapacitatedNetwork V) (sess : UnicastSessions V K) : FlowSupportsRate net sess 0 := by refine ⟨fun _ _ _ => 0, ?_, ?_, ?_⟩ · intro k u v; simp · intro u v huv have hcap : 0 ≤ net.cap s(u, v) := by by_cases h : s(u, v) ∈ net.G.edgeSet · exact le_of_lt (net.cap_pos _ h) · rw [net.cap_zero _ h] simpa using hcap · intro k v simp