graph_min_degree_edge_partition_b_card_le
If 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 ≤ c + 2.
Statement
theorem graph_min_degree_edge_partition_b_card_le {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) (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) : B.card ≤ C.card + 2
- 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
The theorem is proved by real linear arithmetic on the degrees of $x$ and $y$. First, the assumption that the minimum degree is at least $2n/3 - 1$, combined with the partition expressions for $\deg(x)$, $\deg(y)$, and $n = |V|$, yields two linear inequalities: $2|B| + 2|P| \le |A| + |C| + 2$ and $2|A| + 2|P| \le |B| + |C| + 2$. Eliminating $|A|$ from these bounds and using the non-negativity of $|P|$ gives $|B| \le |C| + 2$ in $\mathbb{R}$. Finally, this inequality is cast back to $\mathbb{N}$.
The minimum degree of $G$ is at most the degrees of $x$ and $y$, when cast to the real numbers.
In any finite graph, the minimum degree is at most the degree of any vertex (`SimpleGraph.minDegree_le_degree`). Applying this to $x$ and $y$ and casting to $\mathbb{R}$ establishes $\delta(G) \le \deg(x)$ and $\delta(G) \le \deg(y)$.
uses
SimpleGraph.minDegree_le_degreehave hminx : (G.minDegree : ℝ) ≤ (G.degree x : ℝ) := by exact_mod_cast SimpleGraph.minDegree_le_degree G x have hminy : (G.minDegree : ℝ) ≤ (G.degree y : ℝ) := by exact_mod_cast SimpleGraph.minDegree_le_degree G y
The degree formulas for $x$ and $y$ and the vertex count formula hold as equalities in $\mathbb{R}$.
The given hypotheses $\deg(x) = |A| + |C| + 1$, $\deg(y) = |B| + |C| + 1$, and $|V| = 2 + |A| + |B| + |C| + |P|$ are cast from the natural numbers into the real numbers to prepare for linear arithmetic.
have hdxR : (G.degree x : ℝ) = (A.card : ℝ) + (C.card : ℝ) + 1 := by exact_mod_cast hdx have hdyR : (G.degree y : ℝ) = (B.card : ℝ) + (C.card : ℝ) + 1 := by exact_mod_cast hdy have hnR : (Fintype.card V : ℝ) = 2 + (A.card : ℝ) + (B.card : ℝ) + (C.card : ℝ) + (P.card : ℝ) := by exact_mod_cast hn
$2|B| + 2|P| \le |A| + |C| + 2$ in $\mathbb{R}$.
Combining the lower bound $\deg(x) \ge \delta(G) \ge \frac{2|V|}{3} - 1$ with $\deg(x) = |A| + |C| + 1$ and $|V| = 2 + |A| + |B| + |C| + |P|$ gives $|A| + |C| + 1 \ge \frac{2(2 + |A| + |B| + |C| + |P|)}{3} - 1$. Multiplying by 3 and rearranging the terms yields $2|B| + 2|P| \le |A| + |C| + 2$, which is verified by linear arithmetic (`nlinarith`).
have hx : 2 * (B.card : ℝ) + 2 * (P.card : ℝ) ≤ (A.card : ℝ) + (C.card : ℝ) + 2 := by nlinarith
$2|A| + 2|P| \le |B| + |C| + 2$ in $\mathbb{R}$.
Symmetrically, substituting the formulas for $\deg(y)$ and $|V|$ into $\deg(y) \ge \delta(G) \ge \frac{2|V|}{3} - 1$ yields $2|A| + 2|P| \le |B| + |C| + 2$, verified by linear arithmetic (`nlinarith`).
have hy : 2 * (A.card : ℝ) + 2 * (P.card : ℝ) ≤ (B.card : ℝ) + (C.card : ℝ) + 2 := by nlinarith
$|B| \le |C| + 2$ in $\mathbb{R}$.
Multiplying the first inequality by 2 and using the second to eliminate $|A|$ gives $4|B| + 4|P| \le 2|A| + 2|C| + 4 \le (|B| + |C| + 2 - 2|P|) + 2|C| + 4$, which simplifies to $3|B| + 6|P| \le 3|C| + 6$. Since $|P| \ge 0$, this implies $3|B| \le 3|C| + 6$, so $|B| \le |C| + 2$. The linear arithmetic solver (`nlinarith`) closes this goal.
have hb : (B.card : ℝ) ≤ (C.card : ℝ) + 2 := by nlinarith
$|B| \le |C| + 2$ in the natural numbers.
The real inequality $|B| \le |C| + 2$ is cast back to the natural numbers to establish the final goal.
exact_mod_cast hb
SimpleGraph.minDegree_le_degree- In any finite graph, the minimum degree is at most the degree of any vertex.
- The tactic `nlinarith` implicitly uses the non-negativity of natural numbers cast to the reals (namely $|A| \ge 0$ and $|P| \ge 0$) to deduce $|B| \le |C| + 2$ from the two degree bounds.
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.
/-- The minimum-degree hypothesis forces at most two more y-private than common neighbours. -/theorem graph_min_degree_edge_partition_b_card_le {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) (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) : B.card ≤ C.card + 2 := by have hminx : (G.minDegree : ℝ) ≤ (G.degree x : ℝ) := by exact_mod_cast SimpleGraph.minDegree_le_degree G x have hminy : (G.minDegree : ℝ) ≤ (G.degree y : ℝ) := by exact_mod_cast SimpleGraph.minDegree_le_degree G y have hdxR : (G.degree x : ℝ) = (A.card : ℝ) + (C.card : ℝ) + 1 := by exact_mod_cast hdx have hdyR : (G.degree y : ℝ) = (B.card : ℝ) + (C.card : ℝ) + 1 := by exact_mod_cast hdy have hnR : (Fintype.card V : ℝ) = 2 + (A.card : ℝ) + (B.card : ℝ) + (C.card : ℝ) + (P.card : ℝ) := by exact_mod_cast hn have hx : 2 * (B.card : ℝ) + 2 * (P.card : ℝ) ≤ (A.card : ℝ) + (C.card : ℝ) + 2 := by nlinarith have hy : 2 * (A.card : ℝ) + 2 * (P.card : ℝ) ≤ (B.card : ℝ) + (C.card : ℝ) + 2 := by nlinarith have hb : (B.card : ℝ) ≤ (C.card : ℝ) + 2 := by nlinarith exact_mod_cast hb