AFTD Auto-Formalizing Theoretical Domains

flow_supports_rate_zero

theoremverified

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

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

    line 5

      refine ⟨fun _ _ _ => 0, ?_, ?_, ?_⟩
  2. 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.

    line 6

      · intro k u v; simp
  3. 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.

    lines 7–12

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

    lines 13–14

      · 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

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