Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 7 core: a haven yields the large tame cloud and balanced separation

Proved
DvorakNorin2018.haven_cloud_balanced_configuration

by lreyzin · Nov 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

flowsgraph-theorytreewidth

Let GGG be a finite graph, let a≥1a\ge1a≥1, and suppose that every induced subgraph has a balanced separation of order at most aaa. Let β\betaβ be a haven of order k>15ak>15ak>15a. Then there is a lexicographically minimum deletion set WWW of size 14a14a14a, a vertex set XXX, and a tame WWW-cloud on G−β(W)G-\beta(W)G−β(W), of congestion at most α=14∣β(W)∣/(7a)\alpha=14|\beta(W)|/(7a)α=14∣β(W)∣/(7a) and total supply greater than 14∣β(W)∣14|\beta(W)|14∣β(W)∣. The set XXX consists exactly of its hungry or saturated vertices; all supply and incoming and outgoing flow vanish outside XXX. Moreover, W⊆XW\subseteq XW⊆X, X∩β(W)=∅X\cap\beta(W)=\varnothingX∩β(W)=∅, and (X,W∪β(W))(X,W\cup\beta(W))(X,W∪β(W)) is a separation of the induced graph on X∪β(W)X\cup\beta(W)X∪β(W) with intersection WWW. There is a balanced three-part separation L,S,RL,S,RL,S,R of this induced graph, with ∣S∣≤a|S|\le a∣S∣≤a, satisfying

∣(L∩W)∪(S∩X)∣≤a.|(L\cap W)\cup(S\cap X)|\le a.∣(L∩W)∪(S∩X)∣≤a.

Here balanced means 3∣L∣,3∣R∣≤2∣X∪β(W)∣3|L|,3|R|\le2|X\cup\beta(W)|3∣L∣,3∣R∣≤2∣X∪β(W)∣. In full-side notation A=L∪SA=L\cup SA=L∪S, B=R∪SB=R\cup SB=R∪S, the last inequality is precisely ∣A∩(W∪B)∩X∣≤a|A\cap(W\cup B)\cap X|\le a∣A∩(W∪B)∩X∣≤a. This is the haven-based core of Dvorak--Norin Lemma 7, after obtaining the haven; the treewidth-to-haven duality is a separate dependency and is not asserted here.

Preamble
import Definitions.Def_DvorakNorin2018_HavenCloudConfiguration
set_option autoImplicit false
open scoped Classical BigOperators
open TreewidthApprox.Pushed StableMSR.Recovery StableMSR.Recovery.Havens
Formal statement
namespace DvorakNorin2018
theorem haven_cloud_balanced_configuration {V : Type} [Fintype V] [DecidableEq V]
    {G : SimpleGraph V} {a k : ℕ} {β : Finset V → Finset V}
    (hβ : Haven G k β) (hsep : HasBalancedSeparations G a) (ha : 1 ≤ a) (hk : 15*a < k) :
    ∃ (W X : Finset V) (p : TameCloud.Data V), IsMinimumCut β (14*a) W ∧
      W.card = 14*a ∧ W ⊆ X ∧ Disjoint X (β W) ∧ X = activeVertices W p ∧
      X ∩ (W ∪ β W) = W ∧ (W ∪ β W) \ W = β W ∧
      IsPartition3 (X ∪ β W) (X \ W) W (β W) ∧ NoEdge G (X \ W) (β W) ∧
      TameCloud.Cloud (outsideGraph G (β W)) W (14*(β W).card/(7*(a : ℝ))) p ∧
      TameCloud.Tame W (14*(β W).card/(7*(a : ℝ))) p ∧
      14*((β W).card : ℝ) < TameCloud.total p ∧
      (∀ v ∉ X, p.1 v = 0 ∧ (∀ u, p.2 (u,v) = 0) ∧ ∀ u, p.2 (v,u) = 0) ∧
      ∃ L S R : Finset V, IsPartition3 (X ∪ β W) L S R ∧ NoEdge G L R ∧
        S.card ≤ a ∧ 3*L.card ≤ 2*(X ∪ β W).card ∧
        3*R.card ≤ 2*(X ∪ β W).card ∧ ((L ∩ W) ∪ (S ∩ X)).card ≤ a := by sorry
end DvorakNorin2018
Source
Dvorak and Norin, Treewidth of graphs with balanced separations, https://arxiv.org/pdf/1408.3869v2, Lemma 7(a),(b) and its proof, PDF pp. 6-7. Formalization starts from the haven obtained in the first sentence, and uses ambient zero-extension of the cloud.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me