AFTD Auto-Formalizing Theoretical Domains

five_vertex_min_degree_two_idle_coupling_bound

theoremverified

In any 5-vertex graph with minimum degree at least 2 and adjacent vertices x and y, the idle measures at α = 1/2 satisfy 1 < 2 S0 + m_xy.

Statement

theorem five_vertex_min_degree_two_idle_coupling_bound {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (hcard : Fintype.card V = 5)
    (hδ : 2 ≤ G.minDegree) (x y : V) (hxy : G.Adj x y) :
    let μ := graph_idle_measure G (1 / 2) x
    let ν := graph_idle_measure G (1 / 2) y
    let S0 := ∑ v, min (μ v) (ν v)
    let μ1 (a : V) := μ a - min (μ a) (ν a)
    let ν1 (b : V) := ν b - min (μ b) (ν b)
    let m_xy := min (μ1 x) (ν1 y)
    1 < 2 * S0 + m_xy
Source
step towards five_vertex_min_degree_two_wasserstein_lt_one
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 1

The proof, explained

The theorem proves that for any two adjacent vertices x and y in a 5-vertex graph with minimum degree at least 2, the idle measures at α = 1/2 satisfy 1 < 2 S₀ + m_xy. Because idle measures are non-negative, S₀ is lower-bounded by summing pointwise minimums over any subset of vertices: summing over {x, y} contributes 1/(2 d(y)) + 1/(2 d(x)), while any common neighbor z adds an extra term min(1/(2 d(x)), 1/(2 d(y))). The proof branches on whether the neighborhoods of x and y are disjoint: if disjoint, the degree sum satisfies d(x) + d(y) ≤ 5, forcing the degrees to be {2, 2} or {2, 3}, which guarantees the inequality; if they intersect, the contribution from the common neighbor combined with the degree bounds 2 ≤ d(x), d(y) ≤ 4 algebraically forces the same strict inequality.

  1. For any common neighbor z of x and y, the idle measures satisfy μ(z) = 1 / (2 d(x)) and ν(z) = 1 / (2 d(y)).

    Since z is adjacent to both x and y, z ≠ x and z ≠ y by the loopless property of simple graphs. Unfolding the definition of graph_idle_measure with α = 1/2, the condition v = x fails while the adjacency condition holds, giving (1 - 1/2) / d(x) = 1 / (2 d(x)), and symmetrically for y.

    lines 8–13

      intro μ ν
      have hzx : z ≠ x := hxz.ne.symm
      have hzy : z ≠ y := hyz.ne.symm
      dsimp [μ, ν, graph_idle_measure]
      simp only [hzx, hzy, hxz, hyz, ↓reduceIte]
      refine ⟨by ring, by ring⟩
  2. For adjacent vertices x and y, the idle measures evaluate to μ(x) = 1/2, μ(y) = 1 / (2 d(x)), ν(y) = 1/2, and ν(x) = 1 / (2 d(y)).

    Because x and y are adjacent, x ≠ y. Evaluating the definition of idle measure directly at the base vertex gives 1/2, and at an adjacent vertex gives (1 - 1/2) / degree = 1 / (2 degree). Minimum degree at least 2 guarantees that both degrees are at least 2.

    lines 23–36

    uses le_trans, SimpleGraph.minDegree_le_degree

      intro μ ν
      have hne : x ≠ y := hxy.ne
      have hne' : y ≠ x := hne.symm
      have hyx : G.Adj y x := hxy.symm
      have hdegx : 2 ≤ G.degree x := le_trans hδ (SimpleGraph.minDegree_le_degree G x)
      have hdegy : 2 ≤ G.degree y := le_trans hδ (SimpleGraph.minDegree_le_degree G y)
      have hμx : μ x = 1 / 2 := by
        dsimp [μ, graph_idle_measure]; simp
      have hμy : μ y = 1 / (2 * (G.degree x : ℝ)) := by
        dsimp [μ, graph_idle_measure]; simp [hne', hxy]; ring
      have hνy : ν y = 1 / 2 := by
        dsimp [ν, graph_idle_measure]; simp
      have hνx : ν x = 1 / (2 * (G.degree y : ℝ)) := by
        dsimp [ν, graph_idle_measure]; simp [hne, hyx]; ring
  3. The pointwise minimums and surpluses at x and y satisfy min(μ(x), ν(x)) = 1 / (2 d(y)), min(μ(y), ν(y)) = 1 / (2 d(x)), μ(x) - min = 1/2 - 1 / (2 d(y)), and ν(y) - min = 1/2 - 1 / (2 d(x)).

    Since d(y) ≥ 2, 1 / (2 d(y)) ≤ 1/4 ≤ 1/2 = μ(x), which implies min(μ(x), ν(x)) = ν(x) = 1 / (2 d(y)). Symmetrically, d(x) ≥ 2 implies min(μ(y), ν(y)) = μ(y) = 1 / (2 d(x)). Subtracting these minimums from μ(x) = 1/2 and ν(y) = 1/2 gives the surplus values.

    lines 37–53

    uses div_le_div_of_nonneg_left, min_eq_right, min_eq_left

      have hle_x : ν x ≤ μ x := by
        rw [hνx, hμx]
        have : (1 : ℝ) / (2 * ↑(G.degree y)) ≤ 1 / (2 * 2) := by
          apply div_le_div_of_nonneg_left (by norm_num) (by norm_num)
          have : (2 : ℝ) ≤ (G.degree y : ℝ) := by exact_mod_cast hdegy
          linarith
        linarith
      have hle_y : μ y ≤ ν y := by
        rw [hμy, hνy]
        have : (1 : ℝ) / (2 * ↑(G.degree x)) ≤ 1 / (2 * 2) := by
          apply div_le_div_of_nonneg_left (by norm_num) (by norm_num)
          have : (2 : ℝ) ≤ (G.degree x : ℝ) := by exact_mod_cast hdegx
          linarith
        linarith
      have hmin_x : min (μ x) (ν x) = ν x := min_eq_right hle_x
      have hmin_y : min (μ y) (ν y) = μ y := min_eq_left hle_y
      refine ⟨by rw [hmin_x, hνx], by rw [hmin_y, hμy], by rw [hmin_x, hμx, hνx], by rw [hmin_y, hνy, hμy]⟩
  4. For pairwise distinct vertices x, y, z, the sum of their pointwise minimums is bounded by S₀: min(μ(x), ν(x)) + min(μ(y), ν(y)) + min(μ(z), ν(z)) ≤ S₀.

    The idle measures μ and ν are non-negative everywhere, so their pointwise minimum is also non-negative. By Finset.sum_le_univ_sum_of_nonneg, the sum of a non-negative function over the three-element subset {x, y, z} cannot exceed the total sum S₀ over all vertices in V.

    lines 62–72

    uses graph_idle_measure_nonneg, le_min, Finset.sum_le_univ_sum_of_nonneg, Finset.sum_insert, Finset.sum_singleton

      intro μ ν S0
      have h_nonneg : ∀ i : V, 0 ≤ min (μ i) (ν i) := by
        intro i
        have hμ : 0 ≤ μ i := graph_idle_measure_nonneg G (1/2) (by norm_num) (by norm_num) x i
        have hν : 0 ≤ ν i := graph_idle_measure_nonneg G (1/2) (by norm_num) (by norm_num) y i
        exact le_min hμ hν
      have h := Finset.sum_le_univ_sum_of_nonneg (s := {x, y, z}) h_nonneg
      have hx : x ∉ ({y, z} : Finset V) := by simp [hxy, hxz]
      have hy : y ∉ ({z} : Finset V) := by simp [hyz]
      rw [Finset.sum_insert hx, Finset.sum_insert hy, Finset.sum_singleton] at h
      linarith
  5. For distinct vertices x and y, the sum of their pointwise minimums satisfies min(μ(x), ν(x)) + min(μ(y), ν(y)) ≤ S₀.

    By the same reasoning as for three vertices, since the pointwise minimum is non-negative everywhere, summing over the two-element subset {x, y} is bounded above by the total sum S₀ over all vertices.

    lines 80–89

    uses graph_idle_measure_nonneg, le_min, Finset.sum_le_univ_sum_of_nonneg, Finset.sum_insert, Finset.sum_singleton

      intro μ ν S0
      have h_nonneg : ∀ i : V, 0 ≤ min (μ i) (ν i) := by
        intro i
        have hμ : 0 ≤ μ i := graph_idle_measure_nonneg G (1/2) (by norm_num) (by norm_num) x i
        have hν : 0 ≤ ν i := graph_idle_measure_nonneg G (1/2) (by norm_num) (by norm_num) y i
        exact le_min hμ hν
      have h := Finset.sum_le_univ_sum_of_nonneg (s := {x, y}) h_nonneg
      have hx : x ∉ ({y} : Finset V) := by simp [hxy]
      rw [Finset.sum_insert hx, Finset.sum_singleton] at h
      linarith
  6. For real degrees dx, dy ∈ [2, 4], the arithmetic inequality 1 < 1/dy + 1/dx + 2 min(1/(2 dx), 1/(2 dy)) + min(1/2 - 1/(2 dy), 1/2 - 1/(2 dx)) holds.

    Split into cases via le_total depending on whether dx ≤ dy or dy ≤ dx. When dx ≤ dy, min(1/(2 dx), 1/(2 dy)) = 1/(2 dy) and min(1/2 - 1/(2 dy), 1/2 - 1/(2 dx)) = 1/2 - 1/(2 dx). The sum simplifies algebraically to 1/2 + 2/dy + 1/(2 dx). Since dy ≤ 4, 2/dy ≥ 1/2, and since dx > 0, 1/(2 dx) > 0, making the total strictly greater than 1. The case dy ≤ dx is symmetric.

    lines 94–130

    uses le_total, min_eq_right, min_eq_left, div_le_div_of_nonneg_left

      rcases le_total dx dy with hle | hle
      · have h1 : min (1 / (2 * dx)) (1 / (2 * dy)) = 1 / (2 * dy) := by
          apply min_eq_right
          apply div_le_div_of_nonneg_left (by norm_num) (by linarith)
          linarith
        have h2 : min (1 / 2 - 1 / (2 * dy)) (1 / 2 - 1 / (2 * dx)) = 1 / 2 - 1 / (2 * dx) := by
          apply min_eq_right
          have : 1 / (2 * dy) ≤ 1 / (2 * dx) := by
            apply div_le_div_of_nonneg_left (by norm_num) (by linarith)
            linarith
          linarith
        rw [h1, h2]
        have : (1 : ℝ) / dy + 1 / dx + 2 * (1 / (2 * dy)) + (1 / 2 - 1 / (2 * dx)) =
               1 / 2 + 2 / dy + 1 / (2 * dx) := by ring
        rw [this]
        have hdy : 2 / dy ≥ 2 / 4 := by
          apply div_le_div_of_nonneg_left (by norm_num) (by linarith) hy4
        have hdx : 1 / (2 * dx) > 0 := by positivity
        linarith
      · have h1 : min (1 / (2 * dx)) (1 / (2 * dy)) = 1 / (2 * dx) := by
          apply min_eq_left
          apply div_le_div_of_nonneg_left (by norm_num) (by linarith)
          linarith
        have h2 : min (1 / 2 - 1 / (2 * dy)) (1 / 2 - 1 / (2 * dx)) = 1 / 2 - 1 / (2 * dy) := by
          apply min_eq_left
          have : 1 / (2 * dx) ≤ 1 / (2 * dy) := by
            apply div_le_div_of_nonneg_left (by norm_num) (by linarith)
            linarith
          linarith
        rw [h1, h2]
        have : (1 : ℝ) / dy + 1 / dx + 2 * (1 / (2 * dx)) + (1 / 2 - 1 / (2 * dy)) =
               1 / 2 + 2 / dx + 1 / (2 * dy) := by ring
        rw [this]
        have hdx : 2 / dx ≥ 2 / 4 := by
          apply div_le_div_of_nonneg_left (by norm_num) (by linarith) hx4
        have hdy : 1 / (2 * dy) > 0 := by positivity
        linarith
  7. For integers nx, ny ≥ 2 with nx + ny ≤ 5, the arithmetic inequality 1 < 1/ny + 1/nx + min(1/2 - 1/(2 ny), 1/2 - 1/(2 nx)) holds.

    Split into cases depending on whether nx ≤ ny or ny ≤ nx. If nx ≤ ny, the integer constraints nx ≥ 2, ny ≥ 2, and nx + ny ≤ 5 force nx = 2 and ny ≤ 3. Substituting nx = 2, the minimum term simplifies to 1/4, and the full expression becomes 3/4 + 1/ny. Because ny ≤ 3, 1/ny ≥ 1/3, giving 3/4 + 1/3 = 13/12 > 1. The symmetric branch ny ≤ nx yields ny = 2 and nx ≤ 3 with the same bound.

    lines 136–181

    uses le_total, min_eq_right, min_eq_left, div_le_div_of_nonneg_left

      intro dx dy
      have hx2_r : (2 : ℝ) ≤ (nx : ℝ) := by exact_mod_cast hx2
      have hy2_r : (2 : ℝ) ≤ (ny : ℝ) := by exact_mod_cast hy2
      rcases le_total nx ny with hle | hle
      · have hx_le : nx ≤ 2 := by omega
        have hx_eq : nx = 2 := by omega
        have hy_le : ny ≤ 3 := by omega
        have hx : dx = 2 := by
          show (nx : ℝ) = 2; exact_mod_cast hx_eq
        have hy : dy ≤ 3 := by
          show (ny : ℝ) ≤ 3; exact_mod_cast hy_le
        have hdx_le_dy : dx ≤ dy := by
          show (nx : ℝ) ≤ (ny : ℝ); exact_mod_cast hle
        have h2 : min (1 / 2 - 1 / (2 * dy)) (1 / 2 - 1 / (2 * dx)) = 1 / 2 - 1 / (2 * dx) := by
          apply min_eq_right
          have : 1 / (2 * dy) ≤ 1 / (2 * dx) := by
            apply div_le_div_of_nonneg_left (by norm_num) (by linarith)
            linarith
          linarith
        rw [h2, hx]
        have : (1 : ℝ) / dy + 1 / 2 + (1 / 2 - 1 / (2 * 2)) = 3 / 4 + 1 / dy := by ring
        rw [this]
        have hdy : 1 / dy ≥ 1 / 3 := by
          apply div_le_div_of_nonneg_left (by norm_num) (by linarith) hy
        linarith
      · have hy_le : ny ≤ 2 := by omega
        have hy_eq : ny = 2 := by omega
        have hx_le : nx ≤ 3 := by omega
        have hy : dy = 2 := by
          show (ny : ℝ) = 2; exact_mod_cast hy_eq
        have hx : dx ≤ 3 := by
          show (nx : ℝ) ≤ 3; exact_mod_cast hx_le
        have hdy_le_dx : dy ≤ dx := by
          show (ny : ℝ) ≤ (nx : ℝ); exact_mod_cast hle
        have h2 : min (1 / 2 - 1 / (2 * dy)) (1 / 2 - 1 / (2 * dx)) = 1 / 2 - 1 / (2 * dy) := by
          apply min_eq_left
          have : 1 / (2 * dx) ≤ 1 / (2 * dy) := by
            apply div_le_div_of_nonneg_left (by norm_num) (by linarith)
            linarith
          linarith
        rw [h2, hy]
        have : (1 : ℝ) / 2 + 1 / dx + (1 / 2 - 1 / (2 * 2)) = 3 / 4 + 1 / dx := by ring
        rw [this]
        have hdx : 1 / dx ≥ 1 / 3 := by
          apply div_le_div_of_nonneg_left (by norm_num) (by linarith) hx
        linarith
  8. The vertex degrees satisfy 2 ≤ d(x), d(y) ≤ 4, and m_xy = min(1/2 - 1/(2 d(y)), 1/2 - 1/(2 d(x))).

    The lower bound degree ≥ 2 follows from the minimum degree hypothesis. The upper bound degree ≤ 4 follows because |V| = 5 and simple graphs have no self-loops, so degree < 5. Substituting the pointwise surplus formulas from the earlier lemma into the definition of m_xy gives the expression.

    lines 194–211

    uses le_trans, SimpleGraph.minDegree_le_degree, five_vertex_min_degree_two_idle_coupling_bound_min_eval_xy

      intro μ ν S0 μ1 ν1 m_xy
      have hne : x ≠ y := hxy.ne
      have hdegx_ge2 : 2 ≤ G.degree x := le_trans hδ (SimpleGraph.minDegree_le_degree G x)
      have hdegy_ge2 : 2 ≤ G.degree y := le_trans hδ (SimpleGraph.minDegree_le_degree G y)
      have hdegx_le4 : G.degree x ≤ 4 := by
        have := G.degree_lt_card_verts x
        omega
      have hdegy_le4 : G.degree y ≤ 4 := by
        have := G.degree_lt_card_verts y
        omega
      have hdx2_r : (2 : ℝ) ≤ (G.degree x : ℝ) := by exact_mod_cast hdegx_ge2
      have hdy2_r : (2 : ℝ) ≤ (G.degree y : ℝ) := by exact_mod_cast hdegy_ge2
      have hdx4_r : (G.degree x : ℝ) ≤ 4 := by exact_mod_cast hdegx_le4
      have hdy4_r : (G.degree y : ℝ) ≤ 4 := by exact_mod_cast hdegy_le4
      have hmin_xy := five_vertex_min_degree_two_idle_coupling_bound_min_eval_xy G hδ x y hxy
      have hm_xy_eq : m_xy = min (1 / 2 - 1 / (2 * (G.degree y : ℝ))) (1 / 2 - 1 / (2 * (G.degree x : ℝ))) := by
        dsimp [m_xy, μ1, ν1]
        rw [hmin_xy.2.2.1, hmin_xy.2.2.2]
  9. If the neighborhoods of x and y are disjoint, then 1 < 2 S₀ + m_xy.

    When the neighborhoods are disjoint, the size of their union is d(x) + d(y) ≤ |V| = 5. The two-vertex bound on S₀ gives S₀ ≥ 1/(2 d(y)) + 1/(2 d(x)), so 2 S₀ ≥ 1/d(y) + 1/d(x). Applying the case 2 arithmetic lemma with d(x) + d(y) ≤ 5 then directly implies 1 < 2 S₀ + m_xy.

    lines 212–231

    uses Finset.card_union_of_disjoint, SimpleGraph.card_neighborFinset_eq_degree, Finset.subset_univ, Finset.card_le_card, Finset.card_univ, five_vertex_min_degree_two_idle_coupling_bound_sum_pair_le_S0, five_vertex_min_degree_two_idle_coupling_bound_case2_arith

      by_cases hdisj : Disjoint (G.neighborFinset x) (G.neighborFinset y)
      · -- Case 2: disjoint neighbors
        have hunion : (G.neighborFinset x ∪ G.neighborFinset y).card = G.degree x + G.degree y := by
          rw [Finset.card_union_of_disjoint hdisj, SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.card_neighborFinset_eq_degree]
        have hsub : G.neighborFinset x ∪ G.neighborFinset y ⊆ Finset.univ := Finset.subset_univ _
        have hle := Finset.card_le_card hsub
        rw [Finset.card_univ, hcard, hunion] at hle
        have hS0_ge : 1 / (2 * (G.degree y : ℝ)) + 1 / (2 * (G.degree x : ℝ)) ≤ S0 := by
          have hpair := five_vertex_min_degree_two_idle_coupling_bound_sum_pair_le_S0 G x y hne
          dsimp [μ, ν, S0] at hpair
          rw [hmin_xy.1, hmin_xy.2.1] at hpair
          exact hpair
        have h2S0 : 1 / (G.degree y : ℝ) + 1 / (G.degree x : ℝ) ≤ 2 * S0 := by
          have : 1 / (G.degree y : ℝ) + 1 / (G.degree x : ℝ) =
              2 * (1 / (2 * (G.degree y : ℝ)) + 1 / (2 * (G.degree x : ℝ))) := by ring
          linarith
        have hbound := five_vertex_min_degree_two_idle_coupling_bound_case2_arith (G.degree x) (G.degree y) hdegx_ge2 hdegy_ge2 hle
        dsimp at hbound
        rw [hm_xy_eq]
        linarith
  10. If the neighborhoods of x and y share a common neighbor, then 1 < 2 S₀ + m_xy.

    If the neighborhoods are not disjoint, there exists a common neighbor z ∈ N(x) ∩ N(y). The vertices x, y, z are pairwise distinct with μ(z) = 1/(2 d(x)) and ν(z) = 1/(2 d(y)). The three-vertex lower bound on S₀ gives 2 S₀ ≥ 1/d(y) + 1/d(x) + 2 min(1/(2 d(x)), 1/(2 d(y))). Together with m_xy and the bounds 2 ≤ d(x), d(y) ≤ 4, the case 1 arithmetic lemma establishes 1 < 2 S₀ + m_xy.

    lines 232–261

    uses Finset.disjoint_iff_inter_eq_empty, Finset.mem_inter, SimpleGraph.mem_neighborFinset, five_vertex_min_degree_two_idle_coupling_bound_idle_eval_common, five_vertex_min_degree_two_idle_coupling_bound_sum_triple_le_S0, five_vertex_min_degree_two_idle_coupling_bound_case1_arith

      · -- Case 1: common neighbor exists
        rw [Finset.disjoint_iff_inter_eq_empty] at hdisj
        have hnonempty : (G.neighborFinset x ∩ G.neighborFinset y).Nonempty :=
          Finset.nonempty_iff_ne_empty.mpr hdisj
        rcases hnonempty with ⟨z, hz⟩
        rw [Finset.mem_inter, SimpleGraph.mem_neighborFinset, SimpleGraph.mem_neighborFinset] at hz
        have hxz : G.Adj x z := hz.1
        have hyz : G.Adj y z := hz.2
        have hzx : z ≠ x := hxz.ne.symm
        have hzy : z ≠ y := hyz.ne.symm
        have hx_ne_z : x ≠ z := hxz.ne
        have hy_ne_z : y ≠ z := hyz.ne
        have hcommon := five_vertex_min_degree_two_idle_coupling_bound_idle_eval_common G x y z hxz hyz
        have hS0_ge : 1 / (2 * (G.degree y : ℝ)) + 1 / (2 * (G.degree x : ℝ)) +
            min (1 / (2 * (G.degree x : ℝ))) (1 / (2 * (G.degree y : ℝ))) ≤ S0 := by
          have htriple := five_vertex_min_degree_two_idle_coupling_bound_sum_triple_le_S0 G x y z hne hx_ne_z hy_ne_z
          dsimp [μ, ν, S0] at htriple
          rw [hmin_xy.1, hmin_xy.2.1, hcommon.1, hcommon.2] at htriple
          exact htriple
        have h2S0 : 1 / (G.degree y : ℝ) + 1 / (G.degree x : ℝ) +
            2 * min (1 / (2 * (G.degree x : ℝ))) (1 / (2 * (G.degree y : ℝ))) ≤ 2 * S0 := by
          have : 1 / (G.degree y : ℝ) + 1 / (G.degree x : ℝ) +
              2 * min (1 / (2 * (G.degree x : ℝ))) (1 / (2 * (G.degree y : ℝ))) =
              2 * (1 / (2 * (G.degree y : ℝ)) + 1 / (2 * (G.degree x : ℝ)) +
                   min (1 / (2 * (G.degree x : ℝ))) (1 / (2 * (G.degree y : ℝ)))) := by ring
          linarith
        have hbound := five_vertex_min_degree_two_idle_coupling_bound_case1_arith (G.degree x : ℝ) (G.degree y : ℝ)
            hdx2_r hdx4_r hdy2_r hdy4_r
        rw [hm_xy_eq]
        linarith
le_trans
If a ≤ b and b ≤ c, then a ≤ c.
SimpleGraph.minDegree_le_degree
In a finite graph, the minimum degree is at most the degree of any vertex.
div_le_div_of_nonneg_left
If 0 ≤ a and 0 < c ≤ b, then a / b ≤ a / c.
min_eq_right
If b ≤ a, then min(a, b) = b.
min_eq_left
If a ≤ b, then min(a, b) = a.
graph_idle_measure_nonneg
For any parameter α ∈ [0, 1], the idle measure at any vertex is everywhere non-negative.
le_min
If c ≤ a and c ≤ b, then c ≤ min(a, b).
Finset.sum_le_univ_sum_of_nonneg
The sum of a non-negative function over a subset of a finite type is at most its sum over all elements.
Finset.sum_insert
If a ∉ s, the sum over {a} ∪ s equals f(a) plus the sum over s.
Finset.sum_singleton
The sum of a function over a singleton {a} is f(a).
le_total
Any two elements in a linear order satisfy a ≤ b or b ≤ a.
five_vertex_min_degree_two_idle_coupling_bound_min_eval_xy
For adjacent vertices x, y in a graph with minimum degree at least 2, min(μ(x), ν(x)) = 1 / (2 d(y)), min(μ(y), ν(y)) = 1 / (2 d(x)), and the surplus values are μ(x) - min = 1/2 - 1 / (2 d(y)) and ν(y) - min = 1/2 - 1 / (2 d(x)).
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
SimpleGraph.card_neighborFinset_eq_degree
The cardinality of the neighborhood finset of v equals the degree of v.
Finset.subset_univ
Every finite set of elements of a finite type is a subset of the universal finset.
Finset.card_le_card
If s ⊆ t, then the cardinality of s is at most the cardinality of t.
Finset.card_univ
The cardinality of the universal finset equals the cardinality of the underlying finite type.
five_vertex_min_degree_two_idle_coupling_bound_sum_pair_le_S0
For distinct vertices x and y, min(μ(x), ν(x)) + min(μ(y), ν(y)) ≤ S₀.
five_vertex_min_degree_two_idle_coupling_bound_case2_arith
For integers nx, ny ≥ 2 with nx + ny ≤ 5, 1 < 1/ny + 1/nx + min(1/2 - 1/(2 ny), 1/2 - 1/(2 nx)).
Finset.disjoint_iff_inter_eq_empty
Two finite sets are disjoint if and only if their intersection is empty.
Finset.mem_inter
An element belongs to the intersection of two finite sets if and only if it belongs to both.
SimpleGraph.mem_neighborFinset
A vertex w is in the neighbor finset of v if and only if v and w are adjacent.
five_vertex_min_degree_two_idle_coupling_bound_idle_eval_common
If z is a common neighbor of x and y, then μ(z) = 1 / (2 d(x)) and ν(z) = 1 / (2 d(y)).
five_vertex_min_degree_two_idle_coupling_bound_sum_triple_le_S0
For pairwise distinct vertices x, y, z, min(μ(x), ν(x)) + min(μ(y), ν(y)) + min(μ(z), ν(z)) ≤ S₀.
five_vertex_min_degree_two_idle_coupling_bound_case1_arith
For real numbers 2 ≤ dx, dy ≤ 4, 1 < 1/dy + 1/dx + 2 min(1/(2 dx), 1/(2 dy)) + min(1/2 - 1/(2 dy), 1/2 - 1/(2 dx)).

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

lemma five_vertex_min_degree_two_idle_coupling_bound_idle_eval_common {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (x y z : V)    (hxz : G.Adj x z) (hyz : G.Adj y z) :    let μ := graph_idle_measure G (1 / 2) x    let ν := graph_idle_measure G (1 / 2) y    μ z = 1 / (2 * (G.degree x : ℝ)) ∧    ν z = 1 / (2 * (G.degree y : ℝ)) := by  intro μ ν  have hzx : z ≠ x := hxz.ne.symm  have hzy : z ≠ y := hyz.ne.symm  dsimp [μ, ν, graph_idle_measure]  simp only [hzx, hzy, hxz, hyz, ↓reduceIte]  refine ⟨by ring, by ring⟩lemma five_vertex_min_degree_two_idle_coupling_bound_min_eval_xy {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (hδ : 2 ≤ G.minDegree) (x y : V) (hxy : G.Adj x y) :    let μ := graph_idle_measure G (1 / 2) x    let ν := graph_idle_measure G (1 / 2) y    min (μ x) (ν x) = 1 / (2 * (G.degree y : ℝ)) ∧    min (μ y) (ν y) = 1 / (2 * (G.degree x : ℝ)) ∧    μ x - min (μ x) (ν x) = 1 / 2 - 1 / (2 * (G.degree y : ℝ)) ∧    ν y - min (μ y) (ν y) = 1 / 2 - 1 / (2 * (G.degree x : ℝ)) := by  intro μ ν  have hne : x ≠ y := hxy.ne  have hne' : y ≠ x := hne.symm  have hyx : G.Adj y x := hxy.symm  have hdegx : 2 ≤ G.degree x := le_trans hδ (SimpleGraph.minDegree_le_degree G x)  have hdegy : 2 ≤ G.degree y := le_trans hδ (SimpleGraph.minDegree_le_degree G y)  have hμx : μ x = 1 / 2 := by    dsimp [μ, graph_idle_measure]; simp  have hμy : μ y = 1 / (2 * (G.degree x : ℝ)) := by    dsimp [μ, graph_idle_measure]; simp [hne', hxy]; ring  have hνy : ν y = 1 / 2 := by    dsimp [ν, graph_idle_measure]; simp  have hνx : ν x = 1 / (2 * (G.degree y : ℝ)) := by    dsimp [ν, graph_idle_measure]; simp [hne, hyx]; ring  have hle_x : ν x ≤ μ x := by    rw [hνx, hμx]    have : (1 : ℝ) / (2 * ↑(G.degree y)) ≤ 1 / (2 * 2) := by      apply div_le_div_of_nonneg_left (by norm_num) (by norm_num)      have : (2 : ℝ) ≤ (G.degree y : ℝ) := by exact_mod_cast hdegy      linarith    linarith  have hle_y : μ y ≤ ν y := by    rw [hμy, hνy]    have : (1 : ℝ) / (2 * ↑(G.degree x)) ≤ 1 / (2 * 2) := by      apply div_le_div_of_nonneg_left (by norm_num) (by norm_num)      have : (2 : ℝ) ≤ (G.degree x : ℝ) := by exact_mod_cast hdegx      linarith    linarith  have hmin_x : min (μ x) (ν x) = ν x := min_eq_right hle_x  have hmin_y : min (μ y) (ν y) = μ y := min_eq_left hle_y  refine ⟨by rw [hmin_x, hνx], by rw [hmin_y, hμy], by rw [hmin_x, hμx, hνx], by rw [hmin_y, hνy, hμy]⟩lemma five_vertex_min_degree_two_idle_coupling_bound_sum_triple_le_S0 {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (x y z : V)    (hxy : x ≠ y) (hxz : x ≠ z) (hyz : y ≠ z) :    let μ := graph_idle_measure G (1 / 2) x    let ν := graph_idle_measure G (1 / 2) y    let S0 := ∑ v, min (μ v) (ν v)    min (μ x) (ν x) + min (μ y) (ν y) + min (μ z) (ν z) ≤ S0 := by  intro μ ν S0  have h_nonneg : ∀ i : V, 0 ≤ min (μ i) (ν i) := by    intro i    have hμ : 0 ≤ μ i := graph_idle_measure_nonneg G (1/2) (by norm_num) (by norm_num) x i    have hν : 0 ≤ ν i := graph_idle_measure_nonneg G (1/2) (by norm_num) (by norm_num) y i    exact le_min hμ hν  have h := Finset.sum_le_univ_sum_of_nonneg (s := {x, y, z}) h_nonneg  have hx : x ∉ ({y, z} : Finset V) := by simp [hxy, hxz]  have hy : y ∉ ({z} : Finset V) := by simp [hyz]  rw [Finset.sum_insert hx, Finset.sum_insert hy, Finset.sum_singleton] at h  linarithlemma five_vertex_min_degree_two_idle_coupling_bound_sum_pair_le_S0 {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (x y : V) (hxy : x ≠ y) :    let μ := graph_idle_measure G (1 / 2) x    let ν := graph_idle_measure G (1 / 2) y    let S0 := ∑ v, min (μ v) (ν v)    min (μ x) (ν x) + min (μ y) (ν y) ≤ S0 := by  intro μ ν S0  have h_nonneg : ∀ i : V, 0 ≤ min (μ i) (ν i) := by    intro i    have hμ : 0 ≤ μ i := graph_idle_measure_nonneg G (1/2) (by norm_num) (by norm_num) x i    have hν : 0 ≤ ν i := graph_idle_measure_nonneg G (1/2) (by norm_num) (by norm_num) y i    exact le_min hμ hν  have h := Finset.sum_le_univ_sum_of_nonneg (s := {x, y}) h_nonneg  have hx : x ∉ ({y} : Finset V) := by simp [hxy]  rw [Finset.sum_insert hx, Finset.sum_singleton] at h  linarithlemma five_vertex_min_degree_two_idle_coupling_bound_case1_arith (dx dy : ℝ) (hx2 : 2 ≤ dx) (hx4 : dx ≤ 4) (hy2 : 2 ≤ dy) (hy4 : dy ≤ 4) :    1 < 1 / dy + 1 / dx + 2 * min (1 / (2 * dx)) (1 / (2 * dy)) +        min (1 / 2 - 1 / (2 * dy)) (1 / 2 - 1 / (2 * dx)) := by  rcases le_total dx dy with hle | hle  · have h1 : min (1 / (2 * dx)) (1 / (2 * dy)) = 1 / (2 * dy) := by      apply min_eq_right      apply div_le_div_of_nonneg_left (by norm_num) (by linarith)      linarith    have h2 : min (1 / 2 - 1 / (2 * dy)) (1 / 2 - 1 / (2 * dx)) = 1 / 2 - 1 / (2 * dx) := by      apply min_eq_right      have : 1 / (2 * dy) ≤ 1 / (2 * dx) := by        apply div_le_div_of_nonneg_left (by norm_num) (by linarith)        linarith      linarith    rw [h1, h2]    have : (1 : ℝ) / dy + 1 / dx + 2 * (1 / (2 * dy)) + (1 / 2 - 1 / (2 * dx)) =           1 / 2 + 2 / dy + 1 / (2 * dx) := by ring    rw [this]    have hdy : 2 / dy ≥ 2 / 4 := by      apply div_le_div_of_nonneg_left (by norm_num) (by linarith) hy4    have hdx : 1 / (2 * dx) > 0 := by positivity    linarith  · have h1 : min (1 / (2 * dx)) (1 / (2 * dy)) = 1 / (2 * dx) := by      apply min_eq_left      apply div_le_div_of_nonneg_left (by norm_num) (by linarith)      linarith    have h2 : min (1 / 2 - 1 / (2 * dy)) (1 / 2 - 1 / (2 * dx)) = 1 / 2 - 1 / (2 * dy) := by      apply min_eq_left      have : 1 / (2 * dx) ≤ 1 / (2 * dy) := by        apply div_le_div_of_nonneg_left (by norm_num) (by linarith)        linarith      linarith    rw [h1, h2]    have : (1 : ℝ) / dy + 1 / dx + 2 * (1 / (2 * dx)) + (1 / 2 - 1 / (2 * dy)) =           1 / 2 + 2 / dx + 1 / (2 * dy) := by ring    rw [this]    have hdx : 2 / dx ≥ 2 / 4 := by      apply div_le_div_of_nonneg_left (by norm_num) (by linarith) hx4    have hdy : 1 / (2 * dy) > 0 := by positivity    linarithlemma five_vertex_min_degree_two_idle_coupling_bound_case2_arith (nx ny : ℕ) (hx2 : 2 ≤ nx) (hy2 : 2 ≤ ny) (hsum : nx + ny ≤ 5) :    let dx : ℝ := nx    let dy : ℝ := ny    1 < 1 / dy + 1 / dx + min (1 / 2 - 1 / (2 * dy)) (1 / 2 - 1 / (2 * dx)) := by  intro dx dy  have hx2_r : (2 : ℝ) ≤ (nx : ℝ) := by exact_mod_cast hx2  have hy2_r : (2 : ℝ) ≤ (ny : ℝ) := by exact_mod_cast hy2  rcases le_total nx ny with hle | hle  · have hx_le : nx ≤ 2 := by omega    have hx_eq : nx = 2 := by omega    have hy_le : ny ≤ 3 := by omega    have hx : dx = 2 := by      show (nx : ℝ) = 2; exact_mod_cast hx_eq    have hy : dy ≤ 3 := by      show (ny : ℝ) ≤ 3; exact_mod_cast hy_le    have hdx_le_dy : dx ≤ dy := by      show (nx : ℝ) ≤ (ny : ℝ); exact_mod_cast hle    have h2 : min (1 / 2 - 1 / (2 * dy)) (1 / 2 - 1 / (2 * dx)) = 1 / 2 - 1 / (2 * dx) := by      apply min_eq_right      have : 1 / (2 * dy) ≤ 1 / (2 * dx) := by        apply div_le_div_of_nonneg_left (by norm_num) (by linarith)        linarith      linarith    rw [h2, hx]    have : (1 : ℝ) / dy + 1 / 2 + (1 / 2 - 1 / (2 * 2)) = 3 / 4 + 1 / dy := by ring    rw [this]    have hdy : 1 / dy ≥ 1 / 3 := by      apply div_le_div_of_nonneg_left (by norm_num) (by linarith) hy    linarith  · have hy_le : ny ≤ 2 := by omega    have hy_eq : ny = 2 := by omega    have hx_le : nx ≤ 3 := by omega    have hy : dy = 2 := by      show (ny : ℝ) = 2; exact_mod_cast hy_eq    have hx : dx ≤ 3 := by      show (nx : ℝ) ≤ 3; exact_mod_cast hx_le    have hdy_le_dx : dy ≤ dx := by      show (ny : ℝ) ≤ (nx : ℝ); exact_mod_cast hle    have h2 : min (1 / 2 - 1 / (2 * dy)) (1 / 2 - 1 / (2 * dx)) = 1 / 2 - 1 / (2 * dy) := by      apply min_eq_left      have : 1 / (2 * dx) ≤ 1 / (2 * dy) := by        apply div_le_div_of_nonneg_left (by norm_num) (by linarith)        linarith      linarith    rw [h2, hy]    have : (1 : ℝ) / 2 + 1 / dx + (1 / 2 - 1 / (2 * 2)) = 3 / 4 + 1 / dx := by ring    rw [this]    have hdx : 1 / dx ≥ 1 / 3 := by      apply div_le_div_of_nonneg_left (by norm_num) (by linarith) hx    linarith/-- Lower bound 1 < 2 S₀ + m_xy for idle measures at α = 1/2 on 5-vertex graphs of minimum degree at least 2. -/theorem five_vertex_min_degree_two_idle_coupling_bound {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (hcard : Fintype.card V = 5)    (hδ : 2 ≤ G.minDegree) (x y : V) (hxy : G.Adj x y) :    let μ := graph_idle_measure G (1 / 2) x    let ν := graph_idle_measure G (1 / 2) y    let S0 := ∑ v, min (μ v) (ν v)    let μ1 (a : V) := μ a - min (μ a) (ν a)    let ν1 (b : V) := ν b - min (μ b) (ν b)    let m_xy := min (μ1 x) (ν1 y)    1 < 2 * S0 + m_xy := by  intro μ ν S0 μ1 ν1 m_xy  have hne : x ≠ y := hxy.ne  have hdegx_ge2 : 2 ≤ G.degree x := le_trans hδ (SimpleGraph.minDegree_le_degree G x)  have hdegy_ge2 : 2 ≤ G.degree y := le_trans hδ (SimpleGraph.minDegree_le_degree G y)  have hdegx_le4 : G.degree x ≤ 4 := by    have := G.degree_lt_card_verts x    omega  have hdegy_le4 : G.degree y ≤ 4 := by    have := G.degree_lt_card_verts y    omega  have hdx2_r : (2 : ℝ) ≤ (G.degree x : ℝ) := by exact_mod_cast hdegx_ge2  have hdy2_r : (2 : ℝ) ≤ (G.degree y : ℝ) := by exact_mod_cast hdegy_ge2  have hdx4_r : (G.degree x : ℝ) ≤ 4 := by exact_mod_cast hdegx_le4  have hdy4_r : (G.degree y : ℝ) ≤ 4 := by exact_mod_cast hdegy_le4  have hmin_xy := five_vertex_min_degree_two_idle_coupling_bound_min_eval_xy G hδ x y hxy  have hm_xy_eq : m_xy = min (1 / 2 - 1 / (2 * (G.degree y : ℝ))) (1 / 2 - 1 / (2 * (G.degree x : ℝ))) := by    dsimp [m_xy, μ1, ν1]    rw [hmin_xy.2.2.1, hmin_xy.2.2.2]  by_cases hdisj : Disjoint (G.neighborFinset x) (G.neighborFinset y)  · -- Case 2: disjoint neighbors    have hunion : (G.neighborFinset x ∪ G.neighborFinset y).card = G.degree x + G.degree y := by      rw [Finset.card_union_of_disjoint hdisj, SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.card_neighborFinset_eq_degree]    have hsub : G.neighborFinset x ∪ G.neighborFinset y ⊆ Finset.univ := Finset.subset_univ _    have hle := Finset.card_le_card hsub    rw [Finset.card_univ, hcard, hunion] at hle    have hS0_ge : 1 / (2 * (G.degree y : ℝ)) + 1 / (2 * (G.degree x : ℝ)) ≤ S0 := by      have hpair := five_vertex_min_degree_two_idle_coupling_bound_sum_pair_le_S0 G x y hne      dsimp [μ, ν, S0] at hpair      rw [hmin_xy.1, hmin_xy.2.1] at hpair      exact hpair    have h2S0 : 1 / (G.degree y : ℝ) + 1 / (G.degree x : ℝ) ≤ 2 * S0 := by      have : 1 / (G.degree y : ℝ) + 1 / (G.degree x : ℝ) =          2 * (1 / (2 * (G.degree y : ℝ)) + 1 / (2 * (G.degree x : ℝ))) := by ring      linarith    have hbound := five_vertex_min_degree_two_idle_coupling_bound_case2_arith (G.degree x) (G.degree y) hdegx_ge2 hdegy_ge2 hle    dsimp at hbound    rw [hm_xy_eq]    linarith  · -- Case 1: common neighbor exists    rw [Finset.disjoint_iff_inter_eq_empty] at hdisj    have hnonempty : (G.neighborFinset x ∩ G.neighborFinset y).Nonempty :=      Finset.nonempty_iff_ne_empty.mpr hdisj    rcases hnonempty with ⟨z, hz⟩    rw [Finset.mem_inter, SimpleGraph.mem_neighborFinset, SimpleGraph.mem_neighborFinset] at hz    have hxz : G.Adj x z := hz.1    have hyz : G.Adj y z := hz.2    have hzx : z ≠ x := hxz.ne.symm    have hzy : z ≠ y := hyz.ne.symm    have hx_ne_z : x ≠ z := hxz.ne    have hy_ne_z : y ≠ z := hyz.ne    have hcommon := five_vertex_min_degree_two_idle_coupling_bound_idle_eval_common G x y z hxz hyz    have hS0_ge : 1 / (2 * (G.degree y : ℝ)) + 1 / (2 * (G.degree x : ℝ)) +        min (1 / (2 * (G.degree x : ℝ))) (1 / (2 * (G.degree y : ℝ))) ≤ S0 := by      have htriple := five_vertex_min_degree_two_idle_coupling_bound_sum_triple_le_S0 G x y z hne hx_ne_z hy_ne_z      dsimp [μ, ν, S0] at htriple      rw [hmin_xy.1, hmin_xy.2.1, hcommon.1, hcommon.2] at htriple      exact htriple    have h2S0 : 1 / (G.degree y : ℝ) + 1 / (G.degree x : ℝ) +        2 * min (1 / (2 * (G.degree x : ℝ))) (1 / (2 * (G.degree y : ℝ))) ≤ 2 * S0 := by      have : 1 / (G.degree y : ℝ) + 1 / (G.degree x : ℝ) +          2 * min (1 / (2 * (G.degree x : ℝ))) (1 / (2 * (G.degree y : ℝ))) =          2 * (1 / (2 * (G.degree y : ℝ)) + 1 / (2 * (G.degree x : ℝ)) +               min (1 / (2 * (G.degree x : ℝ))) (1 / (2 * (G.degree y : ℝ)))) := by ring      linarith    have hbound := five_vertex_min_degree_two_idle_coupling_bound_case1_arith (G.degree x : ℝ) (G.degree y : ℝ)        hdx2_r hdx4_r hdy2_r hdy4_r    rw [hm_xy_eq]    linarith
See it in the graphDiscuss this resultChallenge it