Lemma 6: minimum clouds satisfy the finite rerouting properties
ProvedDvorakNorin2018.minimum_cloud_reroutingflowsgraph-theorytreewidth
Let and fix the total supply . Every lexicographic minimum cloud has no positive flow into a hungry vertex, and every saturated vertex has at most one hungry predecessor carrying positive flow into it. These are precisely properties (i) and (ii) of tameness. This is the finite rerouting part of Lemma 6. The source derives these properties by cancelling directed cycles, shortening a positive-flow path into a hungry vertex, and shifting supply between two hungry predecessors. This theorem does not assume either structural property as a hypothesis.
Preamble
import Definitions.Def_DvorakNorin2018_CloudNormalization set_option autoImplicit false open scoped Classical BigOperators open StableMSR.Recovery.TameCloud
Formal statement
namespace DvorakNorin2018
theorem minimum_cloud_rerouting {V : Type} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (W : Finset V) (α s : ℝ) (hα : 1 < α)
(p : Data V) (hp : IsLexMinimum G W α s p) : ReroutingConclusion W p := by sorry
end DvorakNorin2018
Source
Dvorak–Norin, Treewidth of graphs with balanced separations, https://arxiv.org/pdf/1408.3869v2, Section 2.2, definitions preceding Lemma 6 and its proof (PDF pp. 5–6).