AFTD Auto-Formalizing Theoretical Domains

graph_edge_partition_special_structure

theoremverified

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

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.

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

    line 16

      have hAeqB : A.card = B.card := by omega
  2. 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|).

    lines 17–29

    uses SimpleGraph.minDegree_le_degree, Finset.card_eq_zero.mp

      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, ?_⟩
  3. 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.

    lines 30–34

    uses Finset.card_pos.mp

      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
  4. 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).

    lines 35–47

    uses SimpleGraph.mem_neighborFinset, Finset.mem_univ, Finset.mem_union, Finset.mem_singleton, Finset.mem_erase, Or.inl, Or.inr

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

    lines 48–63

    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_mem

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

    lines 64–71

    uses SimpleGraph.card_neighborFinset_eq_degree, le_trans, Finset.card_le_card, le_of_eq, SimpleGraph.minDegree_le_degree

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

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

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