graph_edge_vertex_partition
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
- exists_idle_measure_wasserstein_dist_lt_one_of_ediam_le_two_and_minDegree_geIn a connected graph of diameter at most 2 with minimum degree at least 2n/3 − 1, for every edge xy there exists α ∈ (0, 1) such that the…
- 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|.
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.
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.
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, ?_, ?_, ?_, ?_, ?_, ?_⟩
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.
· intro v; simp [A] · intro v; simp [B] · intro v; simp [C] · intro v; simp [P]
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.
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
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.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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]