AFTD Auto-Formalizing Theoretical Domains

graph_edge_vertex_partition

theoremverified

For 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 common neighbours C, the remaining vertices P, together with x and y themselves.

Statement

theorem graph_edge_vertex_partition {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),
      (∀ v, v ∈ A ↔ (G.Adj x v ∧ ¬ G.Adj y v ∧ v ≠ y)) ∧
      (∀ v, v ∈ B ↔ (G.Adj y v ∧ ¬ G.Adj x v ∧ v ≠ x)) ∧
      (∀ v, v ∈ C ↔ (G.Adj x v ∧ G.Adj y v)) ∧
      (∀ v, v ∈ P ↔ (¬ G.Adj x v ∧ ¬ G.Adj y v)) ∧
      (Finset.univ : Finset V) = {x} ∪ {y} ∪ A ∪ B ∪ C ∪ P ∧
      x ∉ A ∧ y ∉ A ∧ x ∉ B ∧ y ∉ B ∧ x ∉ C ∧ y ∉ C ∧ x ∉ P ∧ y ∉ P
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
Used by 2

The proof, explained

The proof explicitly constructs the four sets A, B, C, and P by filtering the vertex set V according to adjacency to x and y. Their membership equivalences hold by definition. The theorem then shows that these sets together with {x} and {y} cover all vertices by exhaustive case analysis on an arbitrary vertex's adjacency and equality to x and y. Finally, x and y are shown to be disjoint from all four sets using the irreflexivity of simple graphs and the fact that x and y are adjacent.

  1. We define candidate subsets A, B, C, P of V and reduce the goal to proving six subgoals.

    The sets are constructed by filtering the universal finset `Finset.univ` according to the required relations: A contains vertices adjacent to x, not y, and distinct from y; B contains vertices adjacent to y, not x, and distinct from x; C contains common neighbours of x and y; and P contains non-neighbours of both. Supplying these witnesses leaves six obligations: the four membership characterizations, the partition identity, and the non-membership of x and y in all four sets.

    lines 11–16

      classical
      let A : Finset V := Finset.univ.filter (fun v => G.Adj x v ∧ ¬ G.Adj y v ∧ v ≠ y)
      let B : Finset V := Finset.univ.filter (fun v => G.Adj y v ∧ ¬ G.Adj x v ∧ v ≠ x)
      let C : Finset V := Finset.univ.filter (fun v => G.Adj x v ∧ G.Adj y v)
      let P : Finset V := Finset.univ.filter (fun v => ¬ G.Adj x v ∧ ¬ G.Adj y v)
      refine ⟨A, B, C, P, ?_, ?_, ?_, ?_, ?_, ?_⟩
  2. Each of the four sets A, B, C, P satisfies its defining membership equivalence.

    For each set, membership of an arbitrary vertex v simplifies directly by definition to the condition defining the filter, since every vertex belongs to the universe.

    lines 17–20

      · intro v; simp [A]
      · intro v; simp [B]
      · intro v; simp [C]
      · intro v; simp [P]
  3. The union {x} ∪ {y} ∪ A ∪ B ∪ C ∪ P equals the entire vertex set.

    By extensionality, we show that every vertex v belongs to this union. Unfolding the definitions of union, singletons, and filtered sets turns the goal into a disjunction. An exhaustive case split on four conditions—whether v is adjacent to x, whether v is adjacent to y, whether v = x, and whether v = y—produces 16 subcases, each of which immediately satisfies one of the disjuncts.

    lines 21–24

    uses Finset.mem_univ, Finset.mem_union, Finset.mem_singleton, Finset.mem_filter, true_and

      · ext v
        simp only [Finset.mem_univ, Finset.mem_union, Finset.mem_singleton, A, B, C, P,
          Finset.mem_filter, true_and]
        by_cases hx : G.Adj x v <;> by_cases hy : G.Adj y v <;> by_cases hvx : v = x <;> by_cases hvy : v = y <;> simp_all
  4. Neither x nor y belongs to any of the four sets A, B, C, or P.

    Membership of x or y in A, B, or C would require a self-loop (contradicting `SimpleGraph.irrefl`) or self-inequality (x ≠ x or y ≠ y). Membership of x or y in P would require non-adjacency to both x and y, which directly contradicts the assumption hxy that x and y are adjacent.

    line 25

    uses SimpleGraph.irrefl

      · simp [A, B, C, P, hxy, hxy.symm, SimpleGraph.irrefl]
Finset.mem_univ
Every element of a finite type belongs to the universal finset `Finset.univ`.
Finset.mem_union
An element belongs to the union of two finsets if and only if it belongs to the first or the second.
Finset.mem_singleton
An element belongs to the singleton set {a} if and only if it equals a.
Finset.mem_filter
An element belongs to `Finset.filter p s` if and only if it belongs to s and satisfies the predicate p.
true_and
The conjunction `True ∧ p` simplifies to `p`.
SimpleGraph.irrefl
In a simple graph, adjacency is irreflexive: no vertex is adjacent to itself.

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 four-part partition of V induced by an edge xy. -/theorem graph_edge_vertex_partition {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),      (∀ v, v ∈ A ↔ (G.Adj x v ∧ ¬ G.Adj y v ∧ v ≠ y)) ∧      (∀ v, v ∈ B ↔ (G.Adj y v ∧ ¬ G.Adj x v ∧ v ≠ x)) ∧      (∀ v, v ∈ C ↔ (G.Adj x v ∧ G.Adj y v)) ∧      (∀ v, v ∈ P ↔ (¬ G.Adj x v ∧ ¬ G.Adj y v)) ∧      (Finset.univ : Finset V) = {x} ∪ {y} ∪ A ∪ B ∪ C ∪ P ∧      x ∉ A ∧ y ∉ A ∧ x ∉ B ∧ y ∉ B ∧ x ∉ C ∧ y ∉ C ∧ x ∉ P ∧ y ∉ P := by  classical  let A : Finset V := Finset.univ.filter (fun v => G.Adj x v ∧ ¬ G.Adj y v ∧ v ≠ y)  let B : Finset V := Finset.univ.filter (fun v => G.Adj y v ∧ ¬ G.Adj x v ∧ v ≠ x)  let C : Finset V := Finset.univ.filter (fun v => G.Adj x v ∧ G.Adj y v)  let P : Finset V := Finset.univ.filter (fun v => ¬ G.Adj x v ∧ ¬ G.Adj y v)  refine ⟨A, B, C, P, ?_, ?_, ?_, ?_, ?_, ?_⟩  · intro v; simp [A]  · intro v; simp [B]  · intro v; simp [C]  · intro v; simp [P]  · ext v    simp only [Finset.mem_univ, Finset.mem_union, Finset.mem_singleton, A, B, C, P,      Finset.mem_filter, true_and]    by_cases hx : G.Adj x v <;> by_cases hy : G.Adj y v <;> by_cases hvx : v = x <;> by_cases hvy : v = y <;> simp_all  · simp [A, B, C, P, hxy, hxy.symm, SimpleGraph.irrefl]
See it in the graphDiscuss this resultChallenge it