AFTD Auto-Formalizing Theoretical Domains

graph_min_degree_edge_partition_b_card_le

theoremverified

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

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}$.

  1. 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)$.

    lines 10–13

    uses SimpleGraph.minDegree_le_degree

      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
  2. 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.

    lines 14–20

      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
  3. $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`).

    lines 21–23

      have hx : 2 * (B.card : ℝ) + 2 * (P.card : ℝ) ≤
          (A.card : ℝ) + (C.card : ℝ) + 2 := by
        nlinarith
  4. $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`).

    lines 24–26

      have hy : 2 * (A.card : ℝ) + 2 * (P.card : ℝ) ≤
          (B.card : ℝ) + (C.card : ℝ) + 2 := by
        nlinarith
  5. $|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.

    lines 27–28

      have hb : (B.card : ℝ) ≤ (C.card : ℝ) + 2 := by
        nlinarith
  6. $|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.

    line 29

      exact_mod_cast hb
SimpleGraph.minDegree_le_degree
In any finite graph, the minimum degree is at most the degree of any vertex.

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

/-- 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
See it in the graphDiscuss this resultChallenge it