graph_edge_partition_special_structure
If 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.
Statement
theorem graph_edge_partition_special_structure {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hδ : (2 * (Fintype.card V : ℝ)) / 3 - 1 ≤ (G.minDegree : ℝ)) (x y : V) (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) (hdx : G.degree x = A.card + C.card + 1) (hdy : G.degree y = B.card + C.card + 1) (hn : Fintype.card V = 2 + A.card + B.card + C.card + P.card) (heq : G.degree x = G.degree y) (hb : B.card = C.card + 2) : P = ∅ ∧ A.card = B.card ∧ (∃ v ∈ A, ∃ u ∈ B, G.Adj v u)
- 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_partition_cardWith 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|.
- Used by 2
- 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_wasserstein_lt_one_of_edge_partitionGiven the edge partition of a graph of diameter at most 2 whose minimum degree is at least 2n/3 − 1, the idleness-1/2 measures at the…
The proof, explained
Equating the degree formulas for x and y immediately yields |A| = |B|. Using the partition of V and the boundary relation |B| = |C| + 2, the minimum degree condition minDegree ≥ 2|V|/3 - 1 forces |P| ≤ 0, so P is empty. Finally, assuming for contradiction that no edge connects A and B, the neighborhood of any chosen vertex u ∈ B can only contain y, other vertices of B, and vertices of C, giving deg u ≤ |B| + |C| = 2|C| + 2. This contradicts the minimum degree requirement minDegree ≥ 2|C| + 3, guaranteeing an edge between A and B.
|A| = |B|
Equating the degree expressions deg x = |A| + |C| + 1 and deg y = |B| + |C| + 1 using deg x = deg y immediately shows |A| = |B| by linear arithmetic.
have hAeqB : A.card = B.card := by omega
P = ∅, leaving only the existence of an edge between A and B to be shown
We cast the cardinality equations into the real numbers: |V| = 2 + 2|B| + |C| + |P| and deg y = |B| + |C| + 1 with |B| = |C| + 2. Substituting these into the minimum degree hypothesis (2|V|/3 - 1 ≤ minDegree ≤ deg y) gives 2|C| + 3 + (2/3)|P| ≤ 2|C| + 3, which forces |P| ≤ 0 and hence P = ∅. We discharge the first two components of the conjunction (P = ∅ and |A| = |B|).
uses
SimpleGraph.minDegree_le_degree,Finset.card_eq_zero.mphave hnR : (Fintype.card V : ℝ) = 2 + (A.card:ℝ) + (B.card:ℝ) + (C.card:ℝ) + (P.card:ℝ) := by rw [hn]; push_cast; ring have hdyR : (G.degree y : ℝ) = (B.card:ℝ) + (C.card:ℝ) + 1 := by rw [hdy]; push_cast; ring have hAbR : (A.card:ℝ) = (B.card:ℝ) := by exact_mod_cast hAeqB have hbR : (B.card:ℝ) = (C.card:ℝ) + 2 := by exact_mod_cast hb have hminy : (G.minDegree : ℝ) ≤ (G.degree y : ℝ) := by exact_mod_cast SimpleGraph.minDegree_le_degree G y have hP0R : (P.card:ℝ) ≤ 0 := by nlinarith [hδ, hminy, hnR, hdyR, hAbR, hbR] have hP0 : P.card = 0 := by have h : P.card ≤ 0 := by exact_mod_cast hP0R omega have hPempty : P = ∅ := Finset.card_eq_zero.mp hP0 refine ⟨hPempty, hAeqB, ?_⟩
Assume for contradiction that no edge connects A and B, and pick a vertex u ∈ B
Assuming no edge connects A and B, every vertex in A is non-adjacent to every vertex in B. Because |B| = |C| + 2 ≥ 2, B is nonempty, so we can pick a vertex u ∈ B. By definition of B, u is not adjacent to x.
uses
Finset.card_pos.mpby_contra hno push Not at hno have hBcard : 0 < B.card := by omega obtain ⟨u, huB⟩ := Finset.card_pos.mp hBcard have hux : ¬ G.Adj x u := ((hBmem u).mp huB).2.1
The neighborhood of u is a subset of {y} ∪ (B \ {u} ∪ C)
Every neighbor v of u must belong to the partition V = {x} ∪ {y} ∪ A ∪ B ∪ C ∪ P. We rule out each alternative: v ≠ x since u is not adjacent to x; v ∉ A by the contradiction assumption; and v ∉ P since P is empty. Since G has no self-loops, if v ∈ B then v ≠ u, so v ∈ B \ {u}. Thus every neighbor lies in {y} ∪ (B \ {u} ∪ C).
uses
SimpleGraph.mem_neighborFinset,Finset.mem_univ,Finset.mem_union,Finset.mem_singleton,Finset.mem_erase,Or.inl,Or.inrhave hsub : G.neighborFinset u ⊆ ({y} ∪ (B.erase u ∪ C) : Finset V) := by intro v hv rw [SimpleGraph.mem_neighborFinset] at hv have hvuniv : v ∈ ({x} ∪ {y} ∪ A ∪ B ∪ C ∪ P : Finset V) := by rw [← hcover]; exact Finset.mem_univ v simp only [Finset.mem_union, Finset.mem_singleton, Finset.mem_erase] at hvuniv ⊢ rcases hvuniv with ((((hx | hy) | hA) | hB) | hC) | hP · subst hx; exact absurd hv.symm hux · exact Or.inl hy · exact absurd hv.symm (hno v hA u huB) · exact Or.inr (Or.inl ⟨(G.ne_of_adj hv).symm, hB⟩) · exact Or.inr (Or.inr hC) · rw [hPempty] at hP; simp at hP
The bounding set {y} ∪ (B \ {u} ∪ C) has cardinality |B| + |C|
Because G is irreflexive, y cannot belong to B or C (as both require adjacency to y). Furthermore, B and C are disjoint because vertices in B are non-adjacent to x while vertices in C are adjacent to x. Hence {y}, B \ {u}, and C are pairwise disjoint. Summing their cardinalities gives 1 + (|B| - 1) + |C| = |B| + |C|.
uses
Finset.disjoint_left,Finset.disjoint_union_right,Finset.disjoint_singleton_left,Finset.mem_of_mem_erase,Finset.disjoint_left.mp,Finset.card_union_of_disjoint,Finset.card_singleton,Finset.card_erase_of_memhave hyB : y ∉ B := fun h => G.irrefl ((hBmem y).mp h).1 have hyC : y ∉ C := fun h => G.irrefl ((hCmem y).mp h).2 have hBCdisj : 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 hd1 : Disjoint ({y} : Finset V) (B.erase u ∪ C) := by rw [Finset.disjoint_union_right, Finset.disjoint_singleton_left, Finset.disjoint_singleton_left] refine ⟨?_, hyC⟩ intro h; exact hyB (Finset.mem_of_mem_erase h) have hd2 : Disjoint (B.erase u) C := by rw [Finset.disjoint_left]; intro v hv hvC exact (Finset.disjoint_left.mp hBCdisj) (Finset.mem_of_mem_erase hv) hvC have hcardS : ({y} ∪ (B.erase u ∪ C) : Finset V).card = B.card + C.card := by rw [Finset.card_union_of_disjoint hd1, Finset.card_union_of_disjoint hd2, Finset.card_singleton, Finset.card_erase_of_mem huB] omega
deg u ≤ |B| + |C| contradicts the minimum degree bound
The degree of u is bounded by the cardinality of its neighborhood, giving deg u ≤ |B| + |C| = 2|C| + 2. However, minDegree ≤ deg u, while the minimum degree condition requires minDegree ≥ 2|V|/3 - 1 = 2(3|C| + 6)/3 - 1 = 2|C| + 3. This forces 2|C| + 3 ≤ 2|C| + 2, a contradiction that finishes the proof.
uses
SimpleGraph.card_neighborFinset_eq_degree,le_trans,Finset.card_le_card,le_of_eq,SimpleGraph.minDegree_le_degreehave hdeg_le : G.degree u ≤ B.card + C.card := by rw [← SimpleGraph.card_neighborFinset_eq_degree] exact le_trans (Finset.card_le_card hsub) (le_of_eq hcardS) have hdegUR : (G.degree u : ℝ) ≤ (B.card:ℝ) + (C.card:ℝ) := by exact_mod_cast hdeg_le have hminu : (G.minDegree : ℝ) ≤ (G.degree u : ℝ) := by exact_mod_cast SimpleGraph.minDegree_le_degree G u have hPcardR : (P.card : ℝ) = 0 := by rw [hP0]; simp nlinarith [hδ, hminu, hdegUR, hnR, hAbR, hbR, hPcardR]
SimpleGraph.minDegree_le_degree- The minimum degree of a graph is at most the degree of any vertex.
Finset.card_eq_zero.mp- A finite set with cardinality zero is empty.
Finset.card_pos.mp- A finite set with strictly positive cardinality is nonempty.
SimpleGraph.mem_neighborFinset- A vertex belongs to the neighbor finset of v if and only if it is adjacent to v.
Finset.mem_univ- Every element of a finite type belongs to the universal finset univ.
Finset.mem_union- An element belongs to the union of two sets if and only if it belongs to either set.
Finset.mem_singleton- An element belongs to the singleton set {a} if and only if it equals a.
Finset.mem_erase- An element belongs to s.erase b if and only if it is in s and not equal to b.
Or.inl- From a proof of a, infer the disjunction a ∨ b.
Or.inr- From a proof of b, infer the disjunction a ∨ b.
Finset.disjoint_left- Two sets are disjoint if and only if no element of the first belongs to the second.
Finset.disjoint_union_right- A set is disjoint from a union t ∪ u if and only if it is disjoint from both t and u.
Finset.disjoint_singleton_left- The singleton {a} is disjoint from s if and only if a ∉ s.
Finset.mem_of_mem_erase- If an element is in s.erase a, then it is in s.
Finset.disjoint_left.mp- If two sets are disjoint, any element in the first set is not in the second.
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_erase_of_mem- Removing an element from a finite set decreases its cardinality by 1.
SimpleGraph.card_neighborFinset_eq_degree- The cardinality of the neighbor finset of a vertex equals its degree.
le_trans- The inequality relation ≤ is transitive.
Finset.card_le_card- A subset has cardinality at most the cardinality of the superset.
le_of_eq- An equality implies the corresponding inequality.
- The deductions on lines 24 and 71 rely on the `nlinarith` tactic to perform real arithmetic combining the minimum degree bound with the vertex partition equations.
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.
/-- In the boundary configuration (equal degrees, |B| = |C|+2) the leftover part P is empty, |A| = |B|, and some A-vertex is adjacent to some B-vertex. -/theorem graph_edge_partition_special_structure {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hδ : (2 * (Fintype.card V : ℝ)) / 3 - 1 ≤ (G.minDegree : ℝ)) (x y : V) (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) (hdx : G.degree x = A.card + C.card + 1) (hdy : G.degree y = B.card + C.card + 1) (hn : Fintype.card V = 2 + A.card + B.card + C.card + P.card) (heq : G.degree x = G.degree y) (hb : B.card = C.card + 2) : P = ∅ ∧ A.card = B.card ∧ (∃ v ∈ A, ∃ u ∈ B, G.Adj v u) := by have hAeqB : A.card = B.card := by omega have hnR : (Fintype.card V : ℝ) = 2 + (A.card:ℝ) + (B.card:ℝ) + (C.card:ℝ) + (P.card:ℝ) := by rw [hn]; push_cast; ring have hdyR : (G.degree y : ℝ) = (B.card:ℝ) + (C.card:ℝ) + 1 := by rw [hdy]; push_cast; ring have hAbR : (A.card:ℝ) = (B.card:ℝ) := by exact_mod_cast hAeqB have hbR : (B.card:ℝ) = (C.card:ℝ) + 2 := by exact_mod_cast hb have hminy : (G.minDegree : ℝ) ≤ (G.degree y : ℝ) := by exact_mod_cast SimpleGraph.minDegree_le_degree G y have hP0R : (P.card:ℝ) ≤ 0 := by nlinarith [hδ, hminy, hnR, hdyR, hAbR, hbR] have hP0 : P.card = 0 := by have h : P.card ≤ 0 := by exact_mod_cast hP0R omega have hPempty : P = ∅ := Finset.card_eq_zero.mp hP0 refine ⟨hPempty, hAeqB, ?_⟩ by_contra hno push Not at hno have hBcard : 0 < B.card := by omega obtain ⟨u, huB⟩ := Finset.card_pos.mp hBcard have hux : ¬ G.Adj x u := ((hBmem u).mp huB).2.1 have hsub : G.neighborFinset u ⊆ ({y} ∪ (B.erase u ∪ C) : Finset V) := by intro v hv rw [SimpleGraph.mem_neighborFinset] at hv have hvuniv : v ∈ ({x} ∪ {y} ∪ A ∪ B ∪ C ∪ P : Finset V) := by rw [← hcover]; exact Finset.mem_univ v simp only [Finset.mem_union, Finset.mem_singleton, Finset.mem_erase] at hvuniv ⊢ rcases hvuniv with ((((hx | hy) | hA) | hB) | hC) | hP · subst hx; exact absurd hv.symm hux · exact Or.inl hy · exact absurd hv.symm (hno v hA u huB) · exact Or.inr (Or.inl ⟨(G.ne_of_adj hv).symm, hB⟩) · exact Or.inr (Or.inr hC) · rw [hPempty] at hP; simp at hP have hyB : y ∉ B := fun h => G.irrefl ((hBmem y).mp h).1 have hyC : y ∉ C := fun h => G.irrefl ((hCmem y).mp h).2 have hBCdisj : 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 hd1 : Disjoint ({y} : Finset V) (B.erase u ∪ C) := by rw [Finset.disjoint_union_right, Finset.disjoint_singleton_left, Finset.disjoint_singleton_left] refine ⟨?_, hyC⟩ intro h; exact hyB (Finset.mem_of_mem_erase h) have hd2 : Disjoint (B.erase u) C := by rw [Finset.disjoint_left]; intro v hv hvC exact (Finset.disjoint_left.mp hBCdisj) (Finset.mem_of_mem_erase hv) hvC have hcardS : ({y} ∪ (B.erase u ∪ C) : Finset V).card = B.card + C.card := by rw [Finset.card_union_of_disjoint hd1, Finset.card_union_of_disjoint hd2, Finset.card_singleton, Finset.card_erase_of_mem huB] omega have hdeg_le : G.degree u ≤ B.card + C.card := by rw [← SimpleGraph.card_neighborFinset_eq_degree] exact le_trans (Finset.card_le_card hsub) (le_of_eq hcardS) have hdegUR : (G.degree u : ℝ) ≤ (B.card:ℝ) + (C.card:ℝ) := by exact_mod_cast hdeg_le have hminu : (G.minDegree : ℝ) ≤ (G.degree u : ℝ) := by exact_mod_cast SimpleGraph.minDegree_le_degree G u have hPcardR : (P.card : ℝ) = 0 := by rw [hP0]; simp nlinarith [hδ, hminu, hdegUR, hnR, hAbR, hbR, hPcardR]