graph_edge_partition_card
With the four-part partition of V induced by an edge xy: deg x = |A| + |C| + 1, deg y = |B| + |C| + 1, and |V| = 2 + |A| + |B| + |C| + |P|.
Statement
theorem graph_edge_partition_card {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (x y : V) (hxy : G.Adj x y) (A B C P : Finset V) (hAmem : ∀ v, v ∈ A ↔ (G.Adj x v ∧ ¬ G.Adj y v ∧ v ≠ y)) (hBmem : ∀ v, v ∈ B ↔ (G.Adj y v ∧ ¬ G.Adj x v ∧ v ≠ x)) (hCmem : ∀ v, v ∈ C ↔ (G.Adj x v ∧ G.Adj y v)) (hPmem : ∀ v, v ∈ P ↔ (¬ G.Adj x v ∧ ¬ G.Adj y v)) (hcover : (Finset.univ : Finset V) = {x} ∪ {y} ∪ A ∪ B ∪ C ∪ P) : G.degree x = A.card + C.card + 1 ∧ G.degree y = B.card + C.card + 1 ∧ Fintype.card V = 2 + A.card + B.card + C.card + P.card
- Source
- step towards exists_idle_measure_wasserstein_dist_lt_one_of_ediam_le_two_and_minDegree_ge
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- graph_edge_vertex_partitionFor an edge xy of a finite simple graph, the vertex set splits into the x-private neighbours A of x, the y-private neighbours B of y, the…
- Used by 7
- graph_min_degree_edge_partition_b_card_leIf the minimum degree is at least 2n/3 − 1 and the edge partition has deg x = a + c + 1, deg y = b + c + 1, n = 2 + a + b + c + p, then b…
- exists_idle_measure_wasserstein_dist_lt_one_of_ediam_le_two_and_minDegree_geIn a connected graph of diameter at most 2 with minimum degree at least 2n/3 − 1, for every edge xy there exists α ∈ (0, 1) such that the…
- graph_idle_special_cost_lt_oneIf a = b, b = c + 2 and d_y = b + c + 1, then 1/2 + 2(a−1)·(1/2)/d_y < 1.
- graph_idle_transport_plan_main_costFor an edge xy in a graph of diameter at most 2, the main plan from μ_x^{1/2} to μ_y^{1/2} costs at most 1/2 − (1/2)/d_x + 2|B|·(1/2)/d_y.
- graph_idle_transport_plan_main_marginalsWith β = (1/2)/d_x, γ = (1/2)/d_y and d_x ≤ d_y, A.card ≤ B.card, the main plan has nonnegative entries, row sums μ_x^{1/2} and column…
- graph_edge_partition_special_structureIf in the edge partition |B| = |C| + 2 and deg x = deg y, then P = ∅, |A| = |B|, and there is an edge between A and B.
- graph_idle_transport_plan_specialIf the edge partition has |A| = |B| ≥ 1, deg x = deg y, |B| = |C|+2 and an A–B edge, then μ_x^{1/2} and μ_y^{1/2} admit a plan of cost at…
The proof, explained
An edge xy in a simple graph partitions the remaining vertices into four sets: those adjacent only to x (A), only to y (B), to both (C), or to neither (P). The proof first shows that {x}, {y}, A, B, C, and P are mutually disjoint. It then identifies the neighborhood of x as A ∪ C ∪ {y} and that of y as B ∪ C ∪ {x}, which immediately yields deg x = |A| + |C| + 1 and deg y = |B| + |C| + 1 by disjoint union additivity. Finally, decomposing the total vertex set into these six disjoint sets shows |V| = 2 + |A| + |B| + |C| + |P|.
x ≠ y, and neither x nor y belongs to A, B, C, or P.
Since x and y are adjacent in a simple graph, irreflxivity of adjacency implies x ≠ y. For any set S among A, B, C, and P, if x or y belonged to S, it would contradict either the irreflxivity of adjacency (no vertex is adjacent to itself) or the non-adjacency and distinctness requirements in the definitions of those sets.
have hxyne : x ≠ y := hxy.ne have hxA : x ∉ A := fun h => G.irrefl ((hAmem x).mp h).1 have hyA : y ∉ A := fun h => ((hAmem y).mp h).2.2 rfl have hxB : x ∉ B := fun h => ((hBmem x).mp h).2.2 rfl have hyB : y ∉ B := fun h => G.irrefl ((hBmem y).mp h).1 have hxC : x ∉ C := fun h => G.irrefl ((hCmem x).mp h).1 have hyC : y ∉ C := fun h => G.irrefl ((hCmem y).mp h).2 have hxP : x ∉ P := fun h => ((hPmem x).mp h).2 hxy.symm have hyP : y ∉ P := fun h => ((hPmem y).mp h).1 hxy
The sets A, B, C, and P are pairwise disjoint.
For any two distinct sets among {A, B, C, P}, having a common element would lead to a contradiction: an element in A ∩ C or A ∩ B would be both adjacent and non-adjacent to y; an element in A ∩ P or C ∩ P would be both adjacent and non-adjacent to x; and an element in B ∩ C or B ∩ P would be both adjacent and non-adjacent to x or y.
uses
Finset.disjoint_lefthave hAC : Disjoint A C := by rw [Finset.disjoint_left]; intro v hvA hvC exact ((hAmem v).mp hvA).2.1 ((hCmem v).mp hvC).2 have hAB : Disjoint A B := by rw [Finset.disjoint_left]; intro v hvA hvB exact ((hAmem v).mp hvA).2.1 ((hBmem v).mp hvB).1 have hAP : Disjoint A P := by rw [Finset.disjoint_left]; intro v hvA hvP exact ((hPmem v).mp hvP).1 ((hAmem v).mp hvA).1 have hBC : Disjoint B C := by rw [Finset.disjoint_left]; intro v hvB hvC exact ((hBmem v).mp hvB).2.1 ((hCmem v).mp hvC).1 have hBP : Disjoint B P := by rw [Finset.disjoint_left]; intro v hvB hvP exact ((hPmem v).mp hvP).2 ((hBmem v).mp hvB).1 have hCP : Disjoint C P := by rw [Finset.disjoint_left]; intro v hvC hvP exact ((hPmem v).mp hvP).1 ((hCmem v).mp hvC).1
The singletons {x} and {y} are disjoint from each other and from each of A, B, C, and P; moreover, A ∪ C is disjoint from {y} and B ∪ C is disjoint from {x}.
Since x ≠ y, the singletons {x} and {y} are disjoint. For any set S ∈ {A, B, C, P}, disjointness of {x} ∪ {y} from S reduces by Finset.disjoint_union_left to x ∉ S and y ∉ S, which were established earlier. Similarly, disjointness of A ∪ C from {y} reduces to y ∉ A and y ∉ C, and disjointness of B ∪ C from {x} reduces to x ∉ B and x ∉ C.
uses
Finset.disjoint_singleton_left,Finset.disjoint_union_left,Finset.disjoint_singleton_righthave hxy_disj_sing : Disjoint ({x} : Finset V) {y} := by rw [Finset.disjoint_singleton_left] simpa using hxyne have hxy_A : Disjoint ({x} ∪ {y} : Finset V) A := by rw [Finset.disjoint_union_left] exact ⟨by rwa [Finset.disjoint_singleton_left], by rwa [Finset.disjoint_singleton_left]⟩ have hxy_B : Disjoint ({x} ∪ {y} : Finset V) B := by rw [Finset.disjoint_union_left] exact ⟨by rwa [Finset.disjoint_singleton_left], by rwa [Finset.disjoint_singleton_left]⟩ have hxy_C : Disjoint ({x} ∪ {y} : Finset V) C := by rw [Finset.disjoint_union_left] exact ⟨by rwa [Finset.disjoint_singleton_left], by rwa [Finset.disjoint_singleton_left]⟩ have hxy_P : Disjoint ({x} ∪ {y} : Finset V) P := by rw [Finset.disjoint_union_left] exact ⟨by rwa [Finset.disjoint_singleton_left], by rwa [Finset.disjoint_singleton_left]⟩ have hACy : Disjoint (A ∪ C) ({y} : Finset V) := by rw [Finset.disjoint_union_left] exact ⟨by rwa [Finset.disjoint_singleton_right], by rwa [Finset.disjoint_singleton_right]⟩ have hBCx : Disjoint (B ∪ C) ({x} : Finset V) := by rw [Finset.disjoint_union_left] exact ⟨by rwa [Finset.disjoint_singleton_right], by rwa [Finset.disjoint_singleton_right]⟩
The neighbor set of x is the union A ∪ C ∪ {y}.
A vertex v is adjacent to x if and only if it is in A ∪ C ∪ {y}. Given x Adj v, if v = y then v ∈ {y}. If v ≠ y, we check whether y Adj v: if so, v is a common neighbor and belongs to C; if not, v satisfies the conditions for membership in A. The reverse inclusion holds because every element of A, C, or {y} is adjacent to x by definition or by the hypothesis x Adj y.
uses
SimpleGraph.mem_neighborFinset,Finset.mem_union,Finset.mem_singleton,Or.inl,Or.inrhave hNx : G.neighborFinset x = A ∪ C ∪ {y} := by ext v simp only [SimpleGraph.mem_neighborFinset, Finset.mem_union, Finset.mem_singleton] constructor · intro hv by_cases hvy : v = y · exact Or.inr hvy · by_cases hyv : G.Adj y v · exact Or.inl (Or.inr ((hCmem v).mpr ⟨hv, hyv⟩)) · exact Or.inl (Or.inl ((hAmem v).mpr ⟨hv, hyv, hvy⟩)) · rintro ((hvA | hvC) | hvy) · exact ((hAmem v).mp hvA).1 · exact ((hCmem v).mp hvC).1 · rw [hvy]; exact hxy
The neighbor set of y is the union B ∪ C ∪ {x}.
Symmetrically, a vertex v is adjacent to y if and only if it is in B ∪ C ∪ {x}. Given y Adj v, if v = x then v ∈ {x}. If v ≠ x, we check whether x Adj v: if so, v ∈ C; if not, v ∈ B. Conversely, every element of B, C, or {x} is adjacent to y, using symmetry of adjacency for x Adj y.
uses
SimpleGraph.mem_neighborFinset,Finset.mem_union,Finset.mem_singleton,Or.inl,Or.inrhave hNy : G.neighborFinset y = B ∪ C ∪ {x} := by ext v simp only [SimpleGraph.mem_neighborFinset, Finset.mem_union, Finset.mem_singleton] constructor · intro hv by_cases hvx : v = x · exact Or.inr hvx · by_cases hxv : G.Adj x v · exact Or.inl (Or.inr ((hCmem v).mpr ⟨hxv, hv⟩)) · exact Or.inl (Or.inl ((hBmem v).mpr ⟨hv, hxv, hvx⟩)) · rintro ((hvB | hvC) | hvx) · exact ((hBmem v).mp hvB).1 · exact ((hCmem v).mp hvC).2 · rw [hvx]; exact hxy.symm
deg x = |A| + |C| + 1 and deg y = |B| + |C| + 1.
The degree of x is the size of its neighborhood N(x) = (A ∪ C) ∪ {y}. Since A ∪ C is disjoint from {y} and A is disjoint from C, the cardinality of the union is the sum of the cardinalities: |A| + |C| + |{y}| = |A| + |C| + 1. The degree of y follows identically from N(y) = (B ∪ C) ∪ {x}.
uses
SimpleGraph.card_neighborFinset_eq_degree,Finset.card_union_of_disjoint,Finset.card_singletonhave hdegx : G.degree x = A.card + C.card + 1 := by rw [← SimpleGraph.card_neighborFinset_eq_degree, hNx, Finset.card_union_of_disjoint hACy, Finset.card_union_of_disjoint hAC, Finset.card_singleton] have hdegy : G.degree y = B.card + C.card + 1 := by rw [← SimpleGraph.card_neighborFinset_eq_degree, hNy, Finset.card_union_of_disjoint hBCx, Finset.card_union_of_disjoint hBC, Finset.card_singleton]
In the cumulative union ({x} ∪ {y} ∪ A ∪ B ∪ C) ∪ P, each set is disjoint from the preceding union.
Using Finset.disjoint_union_left repeatedly, disjointness of ({x} ∪ {y} ∪ A) with B reduces to disjointness of {x, y} with B and A with B. Next, disjointness with C reduces to disjointness of C with {x, y}, with A, and with B. Finally, disjointness with P reduces to disjointness of P with {x, y}, A, B, and C, all of which were previously established.
uses
Finset.disjoint_union_lefthave d2 : Disjoint (({x} ∪ {y}) ∪ A : Finset V) B := by rw [Finset.disjoint_union_left]; exact ⟨hxy_B, hAB⟩ have d3 : Disjoint ((({x} ∪ {y}) ∪ A) ∪ B : Finset V) C := by rw [Finset.disjoint_union_left] refine ⟨?_, hBC⟩ rw [Finset.disjoint_union_left]; exact ⟨hxy_C, hAC⟩ have d4 : Disjoint (((({x} ∪ {y}) ∪ A) ∪ B) ∪ C : Finset V) P := by rw [Finset.disjoint_union_left] refine ⟨?_, hCP⟩ rw [Finset.disjoint_union_left] refine ⟨?_, hBP⟩ rw [Finset.disjoint_union_left]; exact ⟨hxy_P, hAP⟩
|V| = 2 + |A| + |B| + |C| + |P|, completing the proof.
Since {x} ∪ {y} ∪ A ∪ B ∪ C ∪ P covers the entire vertex set V, and each piece in the union is disjoint from the rest, the cardinality of V is the sum of the cardinalities of the six parts: |{x}| + |{y}| + |A| + |B| + |C| + |P| = 1 + 1 + |A| + |B| + |C| + |P| = 2 + |A| + |B| + |C| + |P|. Combining this with the two degree formulas yields the conjunction.
uses
Finset.card_univ,Finset.card_union_of_disjoint,Finset.card_singletonhave hcard : Fintype.card V = 2 + A.card + B.card + C.card + P.card := by rw [← Finset.card_univ, hcover, Finset.card_union_of_disjoint d4, Finset.card_union_of_disjoint d3, Finset.card_union_of_disjoint d2, Finset.card_union_of_disjoint hxy_A, Finset.card_union_of_disjoint hxy_disj_sing, Finset.card_singleton, Finset.card_singleton] exact ⟨hdegx, hdegy, hcard⟩
Finset.disjoint_left- Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.disjoint_singleton_left- A singleton {a} is disjoint from s if and only if a ∉ s.
Finset.disjoint_union_left- A union s ∪ t is disjoint from u if and only if both s and t are disjoint from u.
Finset.disjoint_singleton_right- A set s is disjoint from the singleton {a} if and only if a ∉ s.
SimpleGraph.mem_neighborFinset- A vertex w is in the neighbor finset of v if and only if v and w are adjacent in G.
Finset.mem_union- An element belongs to s ∪ t if and only if it belongs to s or to t.
Finset.mem_singleton- An element belongs to {a} if and only if it equals a.
Or.inl- Given a proof of proposition a, constructs a proof of the disjunction a ∨ b.
Or.inr- Given a proof of proposition b, constructs a proof of the disjunction a ∨ b.
SimpleGraph.card_neighborFinset_eq_degree- The cardinality of the neighbor finset of a vertex v equals the degree of v.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.card_singleton- The cardinality of any singleton set is 1.
Finset.card_univ- The cardinality of the universal finset on α equals Fintype.card α.
- The partition of V is represented formally as a left-associated nested binary union of finsets ({x} ∪ {y} ∪ A ∪ B ∪ C ∪ P); establishing that the cardinality adds up requires proving disjointness step by step at each binary union layer.
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.
/-- Degree and vertex-count identities for the edge partition. -/theorem graph_edge_partition_card {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (x y : V) (hxy : G.Adj x y) (A B C P : Finset V) (hAmem : ∀ v, v ∈ A ↔ (G.Adj x v ∧ ¬ G.Adj y v ∧ v ≠ y)) (hBmem : ∀ v, v ∈ B ↔ (G.Adj y v ∧ ¬ G.Adj x v ∧ v ≠ x)) (hCmem : ∀ v, v ∈ C ↔ (G.Adj x v ∧ G.Adj y v)) (hPmem : ∀ v, v ∈ P ↔ (¬ G.Adj x v ∧ ¬ G.Adj y v)) (hcover : (Finset.univ : Finset V) = {x} ∪ {y} ∪ A ∪ B ∪ C ∪ P) : G.degree x = A.card + C.card + 1 ∧ G.degree y = B.card + C.card + 1 ∧ Fintype.card V = 2 + A.card + B.card + C.card + P.card := by have hxyne : x ≠ y := hxy.ne have hxA : x ∉ A := fun h => G.irrefl ((hAmem x).mp h).1 have hyA : y ∉ A := fun h => ((hAmem y).mp h).2.2 rfl have hxB : x ∉ B := fun h => ((hBmem x).mp h).2.2 rfl have hyB : y ∉ B := fun h => G.irrefl ((hBmem y).mp h).1 have hxC : x ∉ C := fun h => G.irrefl ((hCmem x).mp h).1 have hyC : y ∉ C := fun h => G.irrefl ((hCmem y).mp h).2 have hxP : x ∉ P := fun h => ((hPmem x).mp h).2 hxy.symm have hyP : y ∉ P := fun h => ((hPmem y).mp h).1 hxy have hAC : Disjoint A C := by rw [Finset.disjoint_left]; intro v hvA hvC exact ((hAmem v).mp hvA).2.1 ((hCmem v).mp hvC).2 have hAB : Disjoint A B := by rw [Finset.disjoint_left]; intro v hvA hvB exact ((hAmem v).mp hvA).2.1 ((hBmem v).mp hvB).1 have hAP : Disjoint A P := by rw [Finset.disjoint_left]; intro v hvA hvP exact ((hPmem v).mp hvP).1 ((hAmem v).mp hvA).1 have hBC : Disjoint B C := by rw [Finset.disjoint_left]; intro v hvB hvC exact ((hBmem v).mp hvB).2.1 ((hCmem v).mp hvC).1 have hBP : Disjoint B P := by rw [Finset.disjoint_left]; intro v hvB hvP exact ((hPmem v).mp hvP).2 ((hBmem v).mp hvB).1 have hCP : Disjoint C P := by rw [Finset.disjoint_left]; intro v hvC hvP exact ((hPmem v).mp hvP).1 ((hCmem v).mp hvC).1 have hxy_disj_sing : Disjoint ({x} : Finset V) {y} := by rw [Finset.disjoint_singleton_left] simpa using hxyne have hxy_A : Disjoint ({x} ∪ {y} : Finset V) A := by rw [Finset.disjoint_union_left] exact ⟨by rwa [Finset.disjoint_singleton_left], by rwa [Finset.disjoint_singleton_left]⟩ have hxy_B : Disjoint ({x} ∪ {y} : Finset V) B := by rw [Finset.disjoint_union_left] exact ⟨by rwa [Finset.disjoint_singleton_left], by rwa [Finset.disjoint_singleton_left]⟩ have hxy_C : Disjoint ({x} ∪ {y} : Finset V) C := by rw [Finset.disjoint_union_left] exact ⟨by rwa [Finset.disjoint_singleton_left], by rwa [Finset.disjoint_singleton_left]⟩ have hxy_P : Disjoint ({x} ∪ {y} : Finset V) P := by rw [Finset.disjoint_union_left] exact ⟨by rwa [Finset.disjoint_singleton_left], by rwa [Finset.disjoint_singleton_left]⟩ have hACy : Disjoint (A ∪ C) ({y} : Finset V) := by rw [Finset.disjoint_union_left] exact ⟨by rwa [Finset.disjoint_singleton_right], by rwa [Finset.disjoint_singleton_right]⟩ have hBCx : Disjoint (B ∪ C) ({x} : Finset V) := by rw [Finset.disjoint_union_left] exact ⟨by rwa [Finset.disjoint_singleton_right], by rwa [Finset.disjoint_singleton_right]⟩ have hNx : G.neighborFinset x = A ∪ C ∪ {y} := by ext v simp only [SimpleGraph.mem_neighborFinset, Finset.mem_union, Finset.mem_singleton] constructor · intro hv by_cases hvy : v = y · exact Or.inr hvy · by_cases hyv : G.Adj y v · exact Or.inl (Or.inr ((hCmem v).mpr ⟨hv, hyv⟩)) · exact Or.inl (Or.inl ((hAmem v).mpr ⟨hv, hyv, hvy⟩)) · rintro ((hvA | hvC) | hvy) · exact ((hAmem v).mp hvA).1 · exact ((hCmem v).mp hvC).1 · rw [hvy]; exact hxy have hNy : G.neighborFinset y = B ∪ C ∪ {x} := by ext v simp only [SimpleGraph.mem_neighborFinset, Finset.mem_union, Finset.mem_singleton] constructor · intro hv by_cases hvx : v = x · exact Or.inr hvx · by_cases hxv : G.Adj x v · exact Or.inl (Or.inr ((hCmem v).mpr ⟨hxv, hv⟩)) · exact Or.inl (Or.inl ((hBmem v).mpr ⟨hv, hxv, hvx⟩)) · rintro ((hvB | hvC) | hvx) · exact ((hBmem v).mp hvB).1 · exact ((hCmem v).mp hvC).2 · rw [hvx]; exact hxy.symm have hdegx : G.degree x = A.card + C.card + 1 := by rw [← SimpleGraph.card_neighborFinset_eq_degree, hNx, Finset.card_union_of_disjoint hACy, Finset.card_union_of_disjoint hAC, Finset.card_singleton] have hdegy : G.degree y = B.card + C.card + 1 := by rw [← SimpleGraph.card_neighborFinset_eq_degree, hNy, Finset.card_union_of_disjoint hBCx, Finset.card_union_of_disjoint hBC, Finset.card_singleton] have d2 : Disjoint (({x} ∪ {y}) ∪ A : Finset V) B := by rw [Finset.disjoint_union_left]; exact ⟨hxy_B, hAB⟩ have d3 : Disjoint ((({x} ∪ {y}) ∪ A) ∪ B : Finset V) C := by rw [Finset.disjoint_union_left] refine ⟨?_, hBC⟩ rw [Finset.disjoint_union_left]; exact ⟨hxy_C, hAC⟩ have d4 : Disjoint (((({x} ∪ {y}) ∪ A) ∪ B) ∪ C : Finset V) P := by rw [Finset.disjoint_union_left] refine ⟨?_, hCP⟩ rw [Finset.disjoint_union_left] refine ⟨?_, hBP⟩ rw [Finset.disjoint_union_left]; exact ⟨hxy_P, hAP⟩ have hcard : Fintype.card V = 2 + A.card + B.card + C.card + P.card := by rw [← Finset.card_univ, hcover, Finset.card_union_of_disjoint d4, Finset.card_union_of_disjoint d3, Finset.card_union_of_disjoint d2, Finset.card_union_of_disjoint hxy_A, Finset.card_union_of_disjoint hxy_disj_sing, Finset.card_singleton, Finset.card_singleton] exact ⟨hdegx, hdegy, hcard⟩