AFTD Auto-Formalizing Theoretical Domains

graph_edge_partition_card

theoremverified

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

Statement

theorem graph_edge_partition_card {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (x y : V) (hxy : G.Adj x y)
    (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) :
    G.degree x = A.card + C.card + 1 ∧
      G.degree y = B.card + C.card + 1 ∧
      Fintype.card V = 2 + A.card + B.card + C.card + P.card
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_vertex_partitionFor an edge xy of a finite simple graph, the vertex set splits into the x-private neighbours A of x, the y-private neighbours B of y, the…
Used by 7

The proof, explained

An edge xy in a simple graph partitions the remaining vertices into four sets: those adjacent only to x (A), only to y (B), to both (C), or to neither (P). The proof first shows that {x}, {y}, A, B, C, and P are mutually disjoint. It then identifies the neighborhood of x as A ∪ C ∪ {y} and that of y as B ∪ C ∪ {x}, which immediately yields deg x = |A| + |C| + 1 and deg y = |B| + |C| + 1 by disjoint union additivity. Finally, decomposing the total vertex set into these six disjoint sets shows |V| = 2 + |A| + |B| + |C| + |P|.

  1. x ≠ y, and neither x nor y belongs to A, B, C, or P.

    Since x and y are adjacent in a simple graph, irreflxivity of adjacency implies x ≠ y. For any set S among A, B, C, and P, if x or y belonged to S, it would contradict either the irreflxivity of adjacency (no vertex is adjacent to itself) or the non-adjacency and distinctness requirements in the definitions of those sets.

    lines 13–21

      have hxyne : x ≠ y := hxy.ne
      have hxA : x ∉ A := fun h => G.irrefl ((hAmem x).mp h).1
      have hyA : y ∉ A := fun h => ((hAmem y).mp h).2.2 rfl
      have hxB : x ∉ B := fun h => ((hBmem x).mp h).2.2 rfl
      have hyB : y ∉ B := fun h => G.irrefl ((hBmem y).mp h).1
      have hxC : x ∉ C := fun h => G.irrefl ((hCmem x).mp h).1
      have hyC : y ∉ C := fun h => G.irrefl ((hCmem y).mp h).2
      have hxP : x ∉ P := fun h => ((hPmem x).mp h).2 hxy.symm
      have hyP : y ∉ P := fun h => ((hPmem y).mp h).1 hxy
  2. The sets A, B, C, and P are pairwise disjoint.

    For any two distinct sets among {A, B, C, P}, having a common element would lead to a contradiction: an element in A ∩ C or A ∩ B would be both adjacent and non-adjacent to y; an element in A ∩ P or C ∩ P would be both adjacent and non-adjacent to x; and an element in B ∩ C or B ∩ P would be both adjacent and non-adjacent to x or y.

    lines 22–39

    uses Finset.disjoint_left

      have hAC : Disjoint A C := by
        rw [Finset.disjoint_left]; intro v hvA hvC
        exact ((hAmem v).mp hvA).2.1 ((hCmem v).mp hvC).2
      have hAB : Disjoint A B := by
        rw [Finset.disjoint_left]; intro v hvA hvB
        exact ((hAmem v).mp hvA).2.1 ((hBmem v).mp hvB).1
      have hAP : Disjoint A P := by
        rw [Finset.disjoint_left]; intro v hvA hvP
        exact ((hPmem v).mp hvP).1 ((hAmem v).mp hvA).1
      have hBC : 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 hBP : Disjoint B P := by
        rw [Finset.disjoint_left]; intro v hvB hvP
        exact ((hPmem v).mp hvP).2 ((hBmem v).mp hvB).1
      have hCP : Disjoint C P := by
        rw [Finset.disjoint_left]; intro v hvC hvP
        exact ((hPmem v).mp hvP).1 ((hCmem v).mp hvC).1
  3. The singletons {x} and {y} are disjoint from each other and from each of A, B, C, and P; moreover, A ∪ C is disjoint from {y} and B ∪ C is disjoint from {x}.

    Since x ≠ y, the singletons {x} and {y} are disjoint. For any set S ∈ {A, B, C, P}, disjointness of {x} ∪ {y} from S reduces by Finset.disjoint_union_left to x ∉ S and y ∉ S, which were established earlier. Similarly, disjointness of A ∪ C from {y} reduces to y ∉ A and y ∉ C, and disjointness of B ∪ C from {x} reduces to x ∉ B and x ∉ C.

    lines 40–60

    uses Finset.disjoint_singleton_left, Finset.disjoint_union_left, Finset.disjoint_singleton_right

      have hxy_disj_sing : Disjoint ({x} : Finset V) {y} := by
        rw [Finset.disjoint_singleton_left]
        simpa using hxyne
      have hxy_A : Disjoint ({x} ∪ {y} : Finset V) A := by
        rw [Finset.disjoint_union_left]
        exact ⟨by rwa [Finset.disjoint_singleton_left], by rwa [Finset.disjoint_singleton_left]⟩
      have hxy_B : Disjoint ({x} ∪ {y} : Finset V) B := by
        rw [Finset.disjoint_union_left]
        exact ⟨by rwa [Finset.disjoint_singleton_left], by rwa [Finset.disjoint_singleton_left]⟩
      have hxy_C : Disjoint ({x} ∪ {y} : Finset V) C := by
        rw [Finset.disjoint_union_left]
        exact ⟨by rwa [Finset.disjoint_singleton_left], by rwa [Finset.disjoint_singleton_left]⟩
      have hxy_P : Disjoint ({x} ∪ {y} : Finset V) P := by
        rw [Finset.disjoint_union_left]
        exact ⟨by rwa [Finset.disjoint_singleton_left], by rwa [Finset.disjoint_singleton_left]⟩
      have hACy : Disjoint (A ∪ C) ({y} : Finset V) := by
        rw [Finset.disjoint_union_left]
        exact ⟨by rwa [Finset.disjoint_singleton_right], by rwa [Finset.disjoint_singleton_right]⟩
      have hBCx : Disjoint (B ∪ C) ({x} : Finset V) := by
        rw [Finset.disjoint_union_left]
        exact ⟨by rwa [Finset.disjoint_singleton_right], by rwa [Finset.disjoint_singleton_right]⟩
  4. The neighbor set of x is the union A ∪ C ∪ {y}.

    A vertex v is adjacent to x if and only if it is in A ∪ C ∪ {y}. Given x Adj v, if v = y then v ∈ {y}. If v ≠ y, we check whether y Adj v: if so, v is a common neighbor and belongs to C; if not, v satisfies the conditions for membership in A. The reverse inclusion holds because every element of A, C, or {y} is adjacent to x by definition or by the hypothesis x Adj y.

    lines 61–74

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

      have hNx : G.neighborFinset x = A ∪ C ∪ {y} := by
        ext v
        simp only [SimpleGraph.mem_neighborFinset, Finset.mem_union, Finset.mem_singleton]
        constructor
        · intro hv
          by_cases hvy : v = y
          · exact Or.inr hvy
          · by_cases hyv : G.Adj y v
            · exact Or.inl (Or.inr ((hCmem v).mpr ⟨hv, hyv⟩))
            · exact Or.inl (Or.inl ((hAmem v).mpr ⟨hv, hyv, hvy⟩))
        · rintro ((hvA | hvC) | hvy)
          · exact ((hAmem v).mp hvA).1
          · exact ((hCmem v).mp hvC).1
          · rw [hvy]; exact hxy
  5. The neighbor set of y is the union B ∪ C ∪ {x}.

    Symmetrically, a vertex v is adjacent to y if and only if it is in B ∪ C ∪ {x}. Given y Adj v, if v = x then v ∈ {x}. If v ≠ x, we check whether x Adj v: if so, v ∈ C; if not, v ∈ B. Conversely, every element of B, C, or {x} is adjacent to y, using symmetry of adjacency for x Adj y.

    lines 75–88

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

      have hNy : G.neighborFinset y = B ∪ C ∪ {x} := by
        ext v
        simp only [SimpleGraph.mem_neighborFinset, Finset.mem_union, Finset.mem_singleton]
        constructor
        · intro hv
          by_cases hvx : v = x
          · exact Or.inr hvx
          · by_cases hxv : G.Adj x v
            · exact Or.inl (Or.inr ((hCmem v).mpr ⟨hxv, hv⟩))
            · exact Or.inl (Or.inl ((hBmem v).mpr ⟨hv, hxv, hvx⟩))
        · rintro ((hvB | hvC) | hvx)
          · exact ((hBmem v).mp hvB).1
          · exact ((hCmem v).mp hvC).2
          · rw [hvx]; exact hxy.symm
  6. deg x = |A| + |C| + 1 and deg y = |B| + |C| + 1.

    The degree of x is the size of its neighborhood N(x) = (A ∪ C) ∪ {y}. Since A ∪ C is disjoint from {y} and A is disjoint from C, the cardinality of the union is the sum of the cardinalities: |A| + |C| + |{y}| = |A| + |C| + 1. The degree of y follows identically from N(y) = (B ∪ C) ∪ {x}.

    lines 89–96

    uses SimpleGraph.card_neighborFinset_eq_degree, Finset.card_union_of_disjoint, Finset.card_singleton

      have hdegx : G.degree x = A.card + C.card + 1 := by
        rw [← SimpleGraph.card_neighborFinset_eq_degree, hNx,
          Finset.card_union_of_disjoint hACy, Finset.card_union_of_disjoint hAC,
          Finset.card_singleton]
      have hdegy : G.degree y = B.card + C.card + 1 := by
        rw [← SimpleGraph.card_neighborFinset_eq_degree, hNy,
          Finset.card_union_of_disjoint hBCx, Finset.card_union_of_disjoint hBC,
          Finset.card_singleton]
  7. In the cumulative union ({x} ∪ {y} ∪ A ∪ B ∪ C) ∪ P, each set is disjoint from the preceding union.

    Using Finset.disjoint_union_left repeatedly, disjointness of ({x} ∪ {y} ∪ A) with B reduces to disjointness of {x, y} with B and A with B. Next, disjointness with C reduces to disjointness of C with {x, y}, with A, and with B. Finally, disjointness with P reduces to disjointness of P with {x, y}, A, B, and C, all of which were previously established.

    lines 97–108

    uses Finset.disjoint_union_left

      have d2 : Disjoint (({x} ∪ {y}) ∪ A : Finset V) B := by
        rw [Finset.disjoint_union_left]; exact ⟨hxy_B, hAB⟩
      have d3 : Disjoint ((({x} ∪ {y}) ∪ A) ∪ B : Finset V) C := by
        rw [Finset.disjoint_union_left]
        refine ⟨?_, hBC⟩
        rw [Finset.disjoint_union_left]; exact ⟨hxy_C, hAC⟩
      have d4 : Disjoint (((({x} ∪ {y}) ∪ A) ∪ B) ∪ C : Finset V) P := by
        rw [Finset.disjoint_union_left]
        refine ⟨?_, hCP⟩
        rw [Finset.disjoint_union_left]
        refine ⟨?_, hBP⟩
        rw [Finset.disjoint_union_left]; exact ⟨hxy_P, hAP⟩
  8. |V| = 2 + |A| + |B| + |C| + |P|, completing the proof.

    Since {x} ∪ {y} ∪ A ∪ B ∪ C ∪ P covers the entire vertex set V, and each piece in the union is disjoint from the rest, the cardinality of V is the sum of the cardinalities of the six parts: |{x}| + |{y}| + |A| + |B| + |C| + |P| = 1 + 1 + |A| + |B| + |C| + |P| = 2 + |A| + |B| + |C| + |P|. Combining this with the two degree formulas yields the conjunction.

    lines 109–115

    uses Finset.card_univ, Finset.card_union_of_disjoint, Finset.card_singleton

      have hcard : Fintype.card V = 2 + A.card + B.card + C.card + P.card := by
        rw [← Finset.card_univ, hcover,
          Finset.card_union_of_disjoint d4, Finset.card_union_of_disjoint d3,
          Finset.card_union_of_disjoint d2, Finset.card_union_of_disjoint hxy_A,
          Finset.card_union_of_disjoint hxy_disj_sing, Finset.card_singleton,
          Finset.card_singleton]
      exact ⟨hdegx, hdegy, hcard⟩
Finset.disjoint_left
Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.disjoint_singleton_left
A singleton {a} is disjoint from s if and only if a ∉ s.
Finset.disjoint_union_left
A union s ∪ t is disjoint from u if and only if both s and t are disjoint from u.
Finset.disjoint_singleton_right
A set s is disjoint from the singleton {a} if and only if a ∉ s.
SimpleGraph.mem_neighborFinset
A vertex w is in the neighbor finset of v if and only if v and w are adjacent in G.
Finset.mem_union
An element belongs to s ∪ t if and only if it belongs to s or to t.
Finset.mem_singleton
An element belongs to {a} if and only if it equals a.
Or.inl
Given a proof of proposition a, constructs a proof of the disjunction a ∨ b.
Or.inr
Given a proof of proposition b, constructs a proof of the disjunction a ∨ b.
SimpleGraph.card_neighborFinset_eq_degree
The cardinality of the neighbor finset of a vertex v equals the degree of v.
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_univ
The cardinality of the universal finset on α equals Fintype.card α.

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

/-- Degree and vertex-count identities for the edge partition. -/theorem graph_edge_partition_card {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (x y : V) (hxy : G.Adj x y)    (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) :    G.degree x = A.card + C.card + 1 ∧      G.degree y = B.card + C.card + 1 ∧      Fintype.card V = 2 + A.card + B.card + C.card + P.card := by  have hxyne : x ≠ y := hxy.ne  have hxA : x ∉ A := fun h => G.irrefl ((hAmem x).mp h).1  have hyA : y ∉ A := fun h => ((hAmem y).mp h).2.2 rfl  have hxB : x ∉ B := fun h => ((hBmem x).mp h).2.2 rfl  have hyB : y ∉ B := fun h => G.irrefl ((hBmem y).mp h).1  have hxC : x ∉ C := fun h => G.irrefl ((hCmem x).mp h).1  have hyC : y ∉ C := fun h => G.irrefl ((hCmem y).mp h).2  have hxP : x ∉ P := fun h => ((hPmem x).mp h).2 hxy.symm  have hyP : y ∉ P := fun h => ((hPmem y).mp h).1 hxy  have hAC : Disjoint A C := by    rw [Finset.disjoint_left]; intro v hvA hvC    exact ((hAmem v).mp hvA).2.1 ((hCmem v).mp hvC).2  have hAB : Disjoint A B := by    rw [Finset.disjoint_left]; intro v hvA hvB    exact ((hAmem v).mp hvA).2.1 ((hBmem v).mp hvB).1  have hAP : Disjoint A P := by    rw [Finset.disjoint_left]; intro v hvA hvP    exact ((hPmem v).mp hvP).1 ((hAmem v).mp hvA).1  have hBC : 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 hBP : Disjoint B P := by    rw [Finset.disjoint_left]; intro v hvB hvP    exact ((hPmem v).mp hvP).2 ((hBmem v).mp hvB).1  have hCP : Disjoint C P := by    rw [Finset.disjoint_left]; intro v hvC hvP    exact ((hPmem v).mp hvP).1 ((hCmem v).mp hvC).1  have hxy_disj_sing : Disjoint ({x} : Finset V) {y} := by    rw [Finset.disjoint_singleton_left]    simpa using hxyne  have hxy_A : Disjoint ({x} ∪ {y} : Finset V) A := by    rw [Finset.disjoint_union_left]    exact ⟨by rwa [Finset.disjoint_singleton_left], by rwa [Finset.disjoint_singleton_left]⟩  have hxy_B : Disjoint ({x} ∪ {y} : Finset V) B := by    rw [Finset.disjoint_union_left]    exact ⟨by rwa [Finset.disjoint_singleton_left], by rwa [Finset.disjoint_singleton_left]⟩  have hxy_C : Disjoint ({x} ∪ {y} : Finset V) C := by    rw [Finset.disjoint_union_left]    exact ⟨by rwa [Finset.disjoint_singleton_left], by rwa [Finset.disjoint_singleton_left]⟩  have hxy_P : Disjoint ({x} ∪ {y} : Finset V) P := by    rw [Finset.disjoint_union_left]    exact ⟨by rwa [Finset.disjoint_singleton_left], by rwa [Finset.disjoint_singleton_left]⟩  have hACy : Disjoint (A ∪ C) ({y} : Finset V) := by    rw [Finset.disjoint_union_left]    exact ⟨by rwa [Finset.disjoint_singleton_right], by rwa [Finset.disjoint_singleton_right]⟩  have hBCx : Disjoint (B ∪ C) ({x} : Finset V) := by    rw [Finset.disjoint_union_left]    exact ⟨by rwa [Finset.disjoint_singleton_right], by rwa [Finset.disjoint_singleton_right]⟩  have hNx : G.neighborFinset x = A ∪ C ∪ {y} := by    ext v    simp only [SimpleGraph.mem_neighborFinset, Finset.mem_union, Finset.mem_singleton]    constructor    · intro hv      by_cases hvy : v = y      · exact Or.inr hvy      · by_cases hyv : G.Adj y v        · exact Or.inl (Or.inr ((hCmem v).mpr ⟨hv, hyv⟩))        · exact Or.inl (Or.inl ((hAmem v).mpr ⟨hv, hyv, hvy⟩))    · rintro ((hvA | hvC) | hvy)      · exact ((hAmem v).mp hvA).1      · exact ((hCmem v).mp hvC).1      · rw [hvy]; exact hxy  have hNy : G.neighborFinset y = B ∪ C ∪ {x} := by    ext v    simp only [SimpleGraph.mem_neighborFinset, Finset.mem_union, Finset.mem_singleton]    constructor    · intro hv      by_cases hvx : v = x      · exact Or.inr hvx      · by_cases hxv : G.Adj x v        · exact Or.inl (Or.inr ((hCmem v).mpr ⟨hxv, hv⟩))        · exact Or.inl (Or.inl ((hBmem v).mpr ⟨hv, hxv, hvx⟩))    · rintro ((hvB | hvC) | hvx)      · exact ((hBmem v).mp hvB).1      · exact ((hCmem v).mp hvC).2      · rw [hvx]; exact hxy.symm  have hdegx : G.degree x = A.card + C.card + 1 := by    rw [← SimpleGraph.card_neighborFinset_eq_degree, hNx,      Finset.card_union_of_disjoint hACy, Finset.card_union_of_disjoint hAC,      Finset.card_singleton]  have hdegy : G.degree y = B.card + C.card + 1 := by    rw [← SimpleGraph.card_neighborFinset_eq_degree, hNy,      Finset.card_union_of_disjoint hBCx, Finset.card_union_of_disjoint hBC,      Finset.card_singleton]  have d2 : Disjoint (({x} ∪ {y}) ∪ A : Finset V) B := by    rw [Finset.disjoint_union_left]; exact ⟨hxy_B, hAB⟩  have d3 : Disjoint ((({x} ∪ {y}) ∪ A) ∪ B : Finset V) C := by    rw [Finset.disjoint_union_left]    refine ⟨?_, hBC⟩    rw [Finset.disjoint_union_left]; exact ⟨hxy_C, hAC⟩  have d4 : Disjoint (((({x} ∪ {y}) ∪ A) ∪ B) ∪ C : Finset V) P := by    rw [Finset.disjoint_union_left]    refine ⟨?_, hCP⟩    rw [Finset.disjoint_union_left]    refine ⟨?_, hBP⟩    rw [Finset.disjoint_union_left]; exact ⟨hxy_P, hAP⟩  have hcard : Fintype.card V = 2 + A.card + B.card + C.card + P.card := by    rw [← Finset.card_univ, hcover,      Finset.card_union_of_disjoint d4, Finset.card_union_of_disjoint d3,      Finset.card_union_of_disjoint d2, Finset.card_union_of_disjoint hxy_A,      Finset.card_union_of_disjoint hxy_disj_sing, Finset.card_singleton,      Finset.card_singleton]  exact ⟨hdegx, hdegy, hcard⟩
See it in the graphDiscuss this resultChallenge it