simple_graph_pair_stable_vertex_link_edge_spoke_exchange
In a two-edge-stable graph, for every edge yz of the link at x and every neighbor w of x, another link edge meets yz and avoids w.
Statement
theorem simple_graph_pair_stable_vertex_link_edge_spoke_exchange (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (x : Fin n) (hstable : ∀ e f : Sym2 (Fin n), e ∈ G.edgeSet → f ∈ G.edgeSet → e ≠ f → simple_graph_triangle_packing_number (G.deleteEdges {e,f}) = simple_graph_triangle_packing_number G) (y z w : Fin n) (hy : G.Adj x y) (hz : G.Adj x z) (hyz : G.Adj y z) (hw : G.Adj x w) : ∃ u v, G.Adj x u ∧ G.Adj x v ∧ G.Adj u v ∧ (u = y ∨ u = z ∨ v = y ∨ v = z) ∧ u ≠ w ∧ v ≠ w ∧ s(u,v) ≠ s(y,z)- Source
- Two-edge-stable triangle-packing residual; experiment 20286. The argument does not require an outside maximum packing. No novelty claim.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- simple_graph_triangle_packing_numberν(G): the maximum number of pairwise edge-disjoint triangles of G (two triangles are edge-disjoint when they share at most one vertex).
- simple_graph_maximum_triangle_packing_edge_meetsEvery triangle shares an edge with a member of a maximum edge-disjoint triangle packing.
- Used by 3
- simple_graph_pair_stable_active_vertex_at_least_five_trianglesIn a finite graph whose maximum triangle-packing number survives every two-edge deletion, any vertex that lies in a triangle lies in at…
- simple_graph_pair_stable_private_k4_packing_incidenceLet a maximum packing in a two-edge-stable graph contain abc, with a and b private to that packing triangle. If abcx is a four-clique…
- simple_graph_pair_stable_kernel_link_edge_spoke_exchangeFor an active outside vertex of a maximum packing supported in a support-plus-one-vertex kernel, the local edge/spoke exchange guaranteed…
The proof, explained
To find another link edge at x meeting yz and avoiding w, we delete the link edge yz and the spoke edge xw to form the subgraph H = G \ {yz, xw}. By two-edge-stability, deleting these two distinct edges preserves the triangle packing number, so any maximum triangle packing Q of H is also a maximum triangle packing of G. By maximality, the triangle {x, y, z} must share an edge with some triangle q ∈ Q. Since q is a triangle in H, it contains neither of the deleted edges yz or xw, forcing q to contain x, exactly one of y or z (say v), and a third vertex u distinct from w. The vertices v and u then form the desired link edge at x meeting yz, avoiding w, and distinct from yz.
If a finite set s intersects {a, b, x} in at least two elements, then s contains at least two of a, b, x.
We prove helper lemma in693_two_of_three by contradiction. If no two of a, b, x both belong to s, then any two elements u, v ∈ s ∩ {a, b, x} must be equal, so |s ∩ {a, b, x}| ≤ 1 by Finset.card_le_one.mpr. But by hypothesis |s ∩ {a, b, x}| ≥ 2, which gives a contradiction via omega.
uses
Finset.card_le_one.mpr,Finset.mem_inter,Finset.mem_insert,Finset.mem_singletonclassical by_contra hn have hle : (s ∩ {a,b,x}).card ≤ 1 := by apply Finset.card_le_one.mpr intro u hu v hv simp only [Finset.mem_inter, Finset.mem_insert, Finset.mem_singleton] at hu hv aesop omega
A 3-element set s containing elements a and x contains a third element distinct from both a and x.
We prove helper lemma in693_third by contradiction. If every element of s were equal to a or x, we would have s ⊆ {a, x}. By Finset.card_le_two and Finset.card_le_card, this forces |s| ≤ 2, contradicting |s| = 3.
uses
not_exists,not_and,Finset.mem_insert,Finset.mem_singleton,Finset.card_le_card,Finset.card_le_twoclassical by_contra hn have hsub : s ⊆ {a,x} := by intro y hy simp only [not_exists, not_and] at hn simp only [Finset.mem_insert, Finset.mem_singleton] by_contra hn2 exact hn y hy (by aesop) (by aesop) have hc := Finset.card_le_card hsub have htwo := Finset.card_le_two (a := a) (b := x) omega
The link edge yz and the spoke edge xw are distinct edges of G.
Because G is a simple graph, the vertex x is distinct from its neighbors y, z, w, and y ≠ z since y ~ z. If the undirected edges s(y, z) and s(x, w) were identical, x would belong to s(y, z), forcing x = y or x = z, contradicting the distinctness of x from its neighbors.
classical have hxy : x ≠ y := hy.ne have hxz : x ≠ z := hz.ne have hyz' : y ≠ z := hyz.ne have hxw : x ≠ w := hw.ne have he : s(y,z) ∈ G.edgeSet := hyz have hf : s(x,w) ∈ G.edgeSet := hw have hef : s(y,z) ≠ s(x,w) := by intro h have : x = y ∨ x = z := by have hmem : x ∈ s(y,z) := by rw [h]; simp simpa using hmem rcases this with h | h <;> aesop
The subgraph H = G \ {s(y, z), s(x, w)} admits a maximum triangle packing Q whose size equals the triangle packing number of G.
Deleting the two distinct edges s(y, z) and s(x, w) produces the subgraph H ≤ G. The set A of sizes of triangle packings in H is nonempty (0 ∈ A) and bounded above by Finset.card_le_univ. By Nat.sSup_mem, the supremum is achieved by some packing Q of H, so |Q| = ν(H). By the two-edge-stability hypothesis hstable, ν(H) = ν(G), so |Q| = ν(G).
uses
SimpleGraph.deleteEdges_le,Finset.card_le_univ,Nat.sSup_memlet H := G.deleteEdges {s(y,z), s(x,w)} have hHG : H ≤ G := SimpleGraph.deleteEdges_le (G := G) {s(y,z), s(x,w)} let A : Set ℕ := {k | ∃ Q : Finset (Finset (Fin n)), (∀ t ∈ Q, H.IsNClique 3 t) ∧ (Q : Set (Finset (Fin n))).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ Q.card = k} have hne : A.Nonempty := ⟨0, ∅, by simp, by simp, rfl⟩ have hbdd : BddAbove A := by refine ⟨Fintype.card (Finset (Fin n)), ?_⟩ rintro k ⟨Q, _, _, rfl⟩ exact Finset.card_le_univ Q obtain ⟨Q, hQH, hQpair, hQcard⟩ := Nat.sSup_mem hne hbdd have hQcard' : Q.card = simple_graph_triangle_packing_number G := by change Q.card = simple_graph_triangle_packing_number H at hQcard have hs := hstable s(y,z) s(x,w) he hf hef change simple_graph_triangle_packing_number H = simple_graph_triangle_packing_number G at hs omega
Some triangle q in the packing Q shares at least two vertices with the triangle {y, z, x}.
Since H ≤ G, Q is also a triangle packing in G. Because |Q| = ν(G), Q is a maximum triangle packing of G. By simple_graph_maximum_triangle_packing_edge_meets, every triangle in G must share an edge (at least two vertices) with some member of Q. The vertices {y, z, x} form a triangle in G because x ~ y, x ~ z, and y ~ z; thus some q ∈ Q satisfies |q ∩ {y, z, x}| ≥ 2.
uses
simple_graph_maximum_triangle_packing_edge_meets,Finset.mem_coe,Finset.mem_insert,Finset.mem_singleton,Ne.symmhave hQG : ∀ t ∈ Q, G.IsNClique 3 t := by intro t ht; exact (hQH t ht).mono hHG have hQc := simple_graph_maximum_triangle_packing_edge_meets G Q hQG hQpair hQcard' have htr : G.IsNClique 3 ({y,z,x} : Finset (Fin n)) := by constructor · intro a ha b hb hab simp only [Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] at ha hb rcases ha with rfl | rfl | rfl <;> rcases hb with rfl | rfl | rfl <;> aesop (add safe [hy.symm, hz.symm, hyz.symm]) · simp [hxy, hxz, hyz', Ne.symm hxy, Ne.symm hxz, Ne.symm hyz'] obtain ⟨q, hqQ, hmeet⟩ := hQc {y,z,x} htr
The triangle q contains neither the edge yz nor the edge xw.
Since q ∈ Q, all edges of q belong to the subgraph H = G \ {s(y, z), s(x, w)}. If {y, z} ⊆ q, the edge yz would be present in H, contradicting the deletion of s(y, z) via SimpleGraph.deleteEdges_adj.mp. The same argument shows that {x, w} cannot be a subset of q.
uses
SimpleGraph.deleteEdges_adj.mphave hqcl := hQG q hqQ have havoid : ¬ (y ∈ q ∧ z ∈ q) ∧ ¬ (x ∈ q ∧ w ∈ q) := by constructor · intro h have hadj : H.Adj y z := (hQH q hqQ).isClique h.1 h.2 hyz' have hnot := (SimpleGraph.deleteEdges_adj.mp hadj).2 exact hnot (by simp) · intro h have hadj : H.Adj x w := (hQH q hqQ).isClique h.1 h.2 hxw have hnot := (SimpleGraph.deleteEdges_adj.mp hadj).2 exact hnot (by simp)
The triangle q consists of x, a vertex v ∈ {y, z}, and a third vertex u distinct from w.
By in693_two_of_three, q contains at least two of y, z, x. Since q cannot contain both y and z, it must contain x and one of y or z, say v ∈ {y, z}. Because q is a 3-clique containing v and x with v ≠ x, in693_third guarantees a third vertex u ∈ q distinct from v and x. Furthermore, since x ∈ q and q cannot contain {x, w}, we have w ∉ q, which implies v ≠ w and u ≠ w.
uses
in693_two_of_three,in693_thirdhave hv : ∃ v : Fin n, (v = y ∨ v = z) ∧ v ∈ q ∧ x ∈ q := by rcases in693_two_of_three q y z x hmeet with hyzq | hyx | hzx · exact False.elim (havoid.1 hyzq) · exact ⟨y, Or.inl rfl, hyx.1, hyx.2⟩ · exact ⟨z, Or.inr rfl, hzx.1, hzx.2⟩ obtain ⟨v, hveq, hvq, hxq⟩ := hv have hvx : v ≠ x := by rcases hveq with rfl | rfl <;> aesop obtain ⟨u, huq, huv, hux⟩ := in693_third q v x hqcl.card_eq hvq hxq have hwq : w ∉ q := fun hwq => havoid.2 ⟨hxq, hwq⟩ have hvw : v ≠ w := fun h => hwq (h ▸ hvq) have huw : u ≠ w := fun h => hwq (h ▸ huq)
The pair (v, u) forms an edge in the link of x that meets yz, avoids w, and is distinct from yz.
Since q = {x, v, u} is a triangle in G, x is adjacent to v and u, and v is adjacent to u, making vu an edge in the link of x. It meets yz because v ∈ {y, z}, and it avoids w because v ≠ w and u ≠ w. Finally, the edge vu is in H, whereas yz was deleted from H, so SimpleGraph.deleteEdges_adj.mp implies s(v, u) ≠ s(y, z). Thus (v, u) satisfies all required conditions.
uses
Ne.symm,SimpleGraph.deleteEdges_adj.mphave hvu : H.Adj v u := (hQH q hqQ).isClique hvq huq (Ne.symm huv) have hn := (SimpleGraph.deleteEdges_adj.mp hvu).2 have hne : s(v,u) ≠ s(y,z) := by intro h apply hn simp [h] refine ⟨v,u, hqcl.isClique hxq hvq (Ne.symm hvx), hqcl.isClique hxq huq (Ne.symm hux), hqcl.isClique hvq huq (Ne.symm huv), ?_, hvw, huw, hne⟩ rcases hveq with rfl | rfl <;> simp
Finset.card_le_one.mpr- If any two elements of a finite set are equal, then the set has cardinality at most 1.
Finset.mem_inter- An element belongs to the intersection of two finite sets if and only if it belongs to both sets.
Finset.mem_insert- An element belongs to the insertion of an element into a finite set if and only if it equals the inserted element or already belongs to the set.
Finset.mem_singleton- An element belongs to a singleton set if and only if it equals the unique element of that set.
not_exists- The negation of an existential statement is equivalent to the universal quantification of its negation.
not_and- The negation of a conjunction P ∧ Q is equivalent to the implication P → ¬Q.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is less than or equal to the cardinality of the other.
Finset.card_le_two- The set containing at most two specified elements has cardinality at most 2.
SimpleGraph.deleteEdges_le- Deleting a set of edges from a graph yields a subgraph of the original graph.
Finset.card_le_univ- The cardinality of any finite subset of a finite type is bounded by the cardinality of the whole type.
Nat.sSup_mem- Every nonempty, bounded-above set of natural numbers contains its supremum.
simple_graph_maximum_triangle_packing_edge_meets- Every triangle in a graph shares at least two vertices (an edge) with some triangle in any maximum triangle packing.
Finset.mem_coe- An element belongs to the coercion of a finite set to a set if and only if it belongs to the finite set.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
SimpleGraph.deleteEdges_adj.mp- If two vertices are adjacent in a graph with deleted edges, then they are adjacent in the original graph and their connecting edge was not deleted.
in693_two_of_three- If a set intersects a 3-element set {a, b, x} in at least two elements, it contains at least one of the pairs {a, b}, {a, x}, or {b, x}.
in693_third- In any 3-element set containing elements a and x, there exists an element distinct from both a and x.
- On paper, taking a maximum triangle packing Q is immediate, whereas the formal proof defines the set of packing sizes, proves it is bounded above by Finset.card_le_univ, and invokes Nat.sSup_mem.
- The proof relies on two private combinatorial helper lemmas (in693_two_of_three and in693_third) to establish elementary facts about intersections and complements of 3-element sets that would typically be taken for granted in a mathematical exposition.
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.
open scoped Sym2set_option maxRecDepth 10000set_option maxHeartbeats 3000000private theorem in693_two_of_three {V : Type*} [DecidableEq V] (s : Finset V) (a b x : V) (h : 2 ≤ (s ∩ {a,b,x}).card) : (a ∈ s ∧ b ∈ s) ∨ (a ∈ s ∧ x ∈ s) ∨ (b ∈ s ∧ x ∈ s) := by classical by_contra hn have hle : (s ∩ {a,b,x}).card ≤ 1 := by apply Finset.card_le_one.mpr intro u hu v hv simp only [Finset.mem_inter, Finset.mem_insert, Finset.mem_singleton] at hu hv aesop omegaprivate theorem in693_third {V : Type*} [DecidableEq V] (s : Finset V) (a x : V) (hcard : s.card = 3) (ha : a ∈ s) (hx : x ∈ s) : ∃ y ∈ s, y ≠ a ∧ y ≠ x := by classical by_contra hn have hsub : s ⊆ {a,x} := by intro y hy simp only [not_exists, not_and] at hn simp only [Finset.mem_insert, Finset.mem_singleton] by_contra hn2 exact hn y hy (by aesop) (by aesop) have hc := Finset.card_le_card hsub have htwo := Finset.card_le_two (a := a) (b := x) omegatheorem simple_graph_pair_stable_vertex_link_edge_spoke_exchange (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (x : Fin n) (hstable : ∀ e f : Sym2 (Fin n), e ∈ G.edgeSet → f ∈ G.edgeSet → e ≠ f → simple_graph_triangle_packing_number (G.deleteEdges {e,f}) = simple_graph_triangle_packing_number G) (y z w : Fin n) (hy : G.Adj x y) (hz : G.Adj x z) (hyz : G.Adj y z) (hw : G.Adj x w) : ∃ u v, G.Adj x u ∧ G.Adj x v ∧ G.Adj u v ∧ (u = y ∨ u = z ∨ v = y ∨ v = z) ∧ u ≠ w ∧ v ≠ w ∧ s(u,v) ≠ s(y,z) := by classical have hxy : x ≠ y := hy.ne have hxz : x ≠ z := hz.ne have hyz' : y ≠ z := hyz.ne have hxw : x ≠ w := hw.ne have he : s(y,z) ∈ G.edgeSet := hyz have hf : s(x,w) ∈ G.edgeSet := hw have hef : s(y,z) ≠ s(x,w) := by intro h have : x = y ∨ x = z := by have hmem : x ∈ s(y,z) := by rw [h]; simp simpa using hmem rcases this with h | h <;> aesop let H := G.deleteEdges {s(y,z), s(x,w)} have hHG : H ≤ G := SimpleGraph.deleteEdges_le (G := G) {s(y,z), s(x,w)} let A : Set ℕ := {k | ∃ Q : Finset (Finset (Fin n)), (∀ t ∈ Q, H.IsNClique 3 t) ∧ (Q : Set (Finset (Fin n))).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ Q.card = k} have hne : A.Nonempty := ⟨0, ∅, by simp, by simp, rfl⟩ have hbdd : BddAbove A := by refine ⟨Fintype.card (Finset (Fin n)), ?_⟩ rintro k ⟨Q, _, _, rfl⟩ exact Finset.card_le_univ Q obtain ⟨Q, hQH, hQpair, hQcard⟩ := Nat.sSup_mem hne hbdd have hQcard' : Q.card = simple_graph_triangle_packing_number G := by change Q.card = simple_graph_triangle_packing_number H at hQcard have hs := hstable s(y,z) s(x,w) he hf hef change simple_graph_triangle_packing_number H = simple_graph_triangle_packing_number G at hs omega have hQG : ∀ t ∈ Q, G.IsNClique 3 t := by intro t ht; exact (hQH t ht).mono hHG have hQc := simple_graph_maximum_triangle_packing_edge_meets G Q hQG hQpair hQcard' have htr : G.IsNClique 3 ({y,z,x} : Finset (Fin n)) := by constructor · intro a ha b hb hab simp only [Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] at ha hb rcases ha with rfl | rfl | rfl <;> rcases hb with rfl | rfl | rfl <;> aesop (add safe [hy.symm, hz.symm, hyz.symm]) · simp [hxy, hxz, hyz', Ne.symm hxy, Ne.symm hxz, Ne.symm hyz'] obtain ⟨q, hqQ, hmeet⟩ := hQc {y,z,x} htr have hqcl := hQG q hqQ have havoid : ¬ (y ∈ q ∧ z ∈ q) ∧ ¬ (x ∈ q ∧ w ∈ q) := by constructor · intro h have hadj : H.Adj y z := (hQH q hqQ).isClique h.1 h.2 hyz' have hnot := (SimpleGraph.deleteEdges_adj.mp hadj).2 exact hnot (by simp) · intro h have hadj : H.Adj x w := (hQH q hqQ).isClique h.1 h.2 hxw have hnot := (SimpleGraph.deleteEdges_adj.mp hadj).2 exact hnot (by simp) have hv : ∃ v : Fin n, (v = y ∨ v = z) ∧ v ∈ q ∧ x ∈ q := by rcases in693_two_of_three q y z x hmeet with hyzq | hyx | hzx · exact False.elim (havoid.1 hyzq) · exact ⟨y, Or.inl rfl, hyx.1, hyx.2⟩ · exact ⟨z, Or.inr rfl, hzx.1, hzx.2⟩ obtain ⟨v, hveq, hvq, hxq⟩ := hv have hvx : v ≠ x := by rcases hveq with rfl | rfl <;> aesop obtain ⟨u, huq, huv, hux⟩ := in693_third q v x hqcl.card_eq hvq hxq have hwq : w ∉ q := fun hwq => havoid.2 ⟨hxq, hwq⟩ have hvw : v ≠ w := fun h => hwq (h ▸ hvq) have huw : u ≠ w := fun h => hwq (h ▸ huq) have hvu : H.Adj v u := (hQH q hqQ).isClique hvq huq (Ne.symm huv) have hn := (SimpleGraph.deleteEdges_adj.mp hvu).2 have hne : s(v,u) ≠ s(y,z) := by intro h apply hn simp [h] refine ⟨v,u, hqcl.isClique hxq hvq (Ne.symm hvx), hqcl.isClique hxq huq (Ne.symm hux), hqcl.isClique hvq huq (Ne.symm huv), ?_, hvw, huw, hne⟩ rcases hveq with rfl | rfl <;> simp