Lemma 6: a lexicographically minimum cloud exists
ProvedDvorakNorin2018.lexicographic_cloud_minimumflowsgraph-theorytreewidth
Given any feasible -cloud of prescribed total supply and congestion at most on a finite graph, there exists a cloud of the same supply and congestion bound that lexicographically minimizes total edge flow and then support size minus saturated-vertex count. The secondary objective is expressed as support size plus unsaturated-vertex count, which differs only by a graph-dependent constant. This proves the extremal selection asserted in the first paragraph of Lemma 6: compactness attains the continuous primary objective, and well-ordering selects the secondary optimum.
Preamble
import Definitions.Def_DvorakNorin2018_CloudNormalization set_option autoImplicit false open scoped Classical BigOperators open StableMSR.Recovery.TameCloud
Formal statement
namespace DvorakNorin2018
theorem lexicographic_cloud_minimum {V : Type} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (W : Finset V) (α s : ℝ)
(p : Data V) (hp : Cloud G W α p) (ht : total p = s) :
∃ q : Data V, IsLexMinimum G W α s q := 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).