AFTD Auto-Formalizing Theoretical Domains

simple_graph_pair_stable_vertex_link_edge_spoke_exchange

theoremverified

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
Used by 3

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.

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

    lines 8–15

    uses Finset.card_le_one.mpr, Finset.mem_inter, Finset.mem_insert, Finset.mem_singleton

      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
      omega
  2. 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.

    lines 20–30

    uses not_exists, not_and, Finset.mem_insert, Finset.mem_singleton, Finset.card_le_card, Finset.card_le_two

      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)
      omega
  3. 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.

    lines 33–45

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

    lines 46–61

    uses SimpleGraph.deleteEdges_le, Finset.card_le_univ, Nat.sSup_mem

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

    lines 62–71

    uses simple_graph_maximum_triangle_packing_edge_meets, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton, Ne.symm

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

    lines 72–82

    uses SimpleGraph.deleteEdges_adj.mp

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

    lines 83–93

    uses in693_two_of_three, in693_third

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

    lines 94–102

    uses Ne.symm, SimpleGraph.deleteEdges_adj.mp

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

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

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