AFTD Auto-Formalizing Theoretical Domains

op_193_avoidance_graph

theoremverified

For a family of cycle-vertex sets, there is a graph whose edges are noncycle pairs not contained in any family member; each k-clique is a stable k-set meeting every family member in at most one point.

Statement

theorem op_193_avoidance_graph (m q k : ℕ) (A : Fin q → Finset (Fin m)) :
    ∃ G : SimpleGraph (Fin m),
      (∀ x y, G.Adj x y ↔ x ≠ y ∧ ¬ (SimpleGraph.cycleGraph m).Adj x y ∧
        ∀ j, ¬(x ∈ A j ∧ y ∈ A j)) ∧
      ∀ S : Finset (Fin m), G.IsNClique k S →
        S.card = k ∧ (SimpleGraph.cycleGraph m).IsIndepSet (↑S : Set (Fin m)) ∧
        ∀ j, (S ∩ A j).card ≤ 1
Source
Clique construction for the anchor-avoidance reduction of OP-193.
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

To construct a graph whose edges avoid cycle edges and pairs in the family sets, we define a simple graph on Fin m with the required adjacency conditions. Its symmetry and looplessness are verified directly. Then, any k-clique in this graph has size k, is an independent set of the cycle graph because edges in the graph cannot be cycle edges, and intersects each family set in at most one vertex because edges cannot share a family set.

  1. The adjacency relation of Inbox777Avoid.graph is symmetric.

    Given an edge between x and y, x ≠ y implies y ≠ x by symmetry of inequality. Furthermore, x and y are not adjacent in the cycle graph, so neither are y and x by symmetry of cycle graph adjacency. Finally, no family member contains both x and y, so none contains both y and x.

    lines 6–9

        intro x y h
        refine ⟨h.1.symm, ?_, ?_⟩
        · intro hxy; exact h.2.1 hxy.symm
        · intro j hxy; exact h.2.2 j ⟨hxy.2, hxy.1⟩⟩
  2. Inbox777Avoid.graph contains no self-loops.

    Adjacency between x and x would require x ≠ x, which contradicts reflexivity x = x.

    line 10

      loopless := ⟨by intro x h; exact h.1 rfl⟩
  3. Any k-clique in the graph has size k and forms an independent set in the cycle graph.

    The size of the clique is k by definition. To show it is independent in the cycle graph, consider any two distinct vertices in the clique. Since they form an edge in the graph, by definition they cannot be adjacent in the cycle graph.

    lines 15–17

      refine ⟨hs.card_eq, ?_, ?_⟩
      · intro x hx y hy hxy hxy'
        exact ((hs.isClique hx hy hxy).2.1) hxy'
  4. Any k-clique intersects each family member A j in at most one vertex.

    To show |S ∩ A j| ≤ 1, it suffices by Finset.card_le_one.mpr to show that any two vertices x, y in the intersection are equal. Assuming for contradiction that x ≠ y, they form an edge in the clique, which by definition means no family member contains both x and y. But x, y ∈ A j by Finset.mem_inter.mp, giving a contradiction.

    lines 18–26

    uses Finset.card_le_one.mpr, Finset.mem_inter.mp

      · intro j
        apply Finset.card_le_one.mpr
        intro x hx y hy
        by_contra hxy
        have hxS := (Finset.mem_inter.mp hx).1
        have hyS := (Finset.mem_inter.mp hy).1
        have hxA := (Finset.mem_inter.mp hx).2
        have hyA := (Finset.mem_inter.mp hy).2
        exact ((hs.isClique hxS hyS hxy).2.2 j) ⟨hxA,hyA⟩
  5. There exists a graph with the specified adjacency whose k-cliques satisfy the avoidance properties.

    We instantiate the existential with Inbox777Avoid.graph. Its adjacency matches the definition by reflexivity, and its cliques satisfy the required properties by Inbox777Avoid.clique_avoids.

    line 36

    uses Inbox777Avoid.graph, Inbox777Avoid.clique_avoids

      exact ⟨Inbox777Avoid.graph m q A, (by intros; rfl), Inbox777Avoid.clique_avoids m q A k⟩
Finset.card_le_one.mpr
A finite set has at most one element if and only if any two of its elements are equal.
Finset.mem_inter.mp
If an element belongs to the intersection of two finite sets, it belongs to both sets.
Inbox777Avoid.graph
The graph on cycle vertices whose edges are noncycle pairs not contained in any family member.
Inbox777Avoid.clique_avoids
Every k-clique in Inbox777Avoid.graph has size k, is independent in the cycle graph, and intersects each family member in at most one vertex.

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

namespace Inbox777Avoidvariable (m q : ℕ) (A : Fin q → Finset (Fin m))def graph : SimpleGraph (Fin m) where  Adj x y := x ≠ y ∧ ¬(SimpleGraph.cycleGraph m).Adj x y ∧ ∀ j, ¬(x ∈ A j ∧ y ∈ A j)  symm := ⟨by    intro x y h    refine ⟨h.1.symm, ?_, ?_⟩    · intro hxy; exact h.2.1 hxy.symm    · intro j hxy; exact h.2.2 j ⟨hxy.2, hxy.1⟩⟩  loopless := ⟨by intro x h; exact h.1 rfl⟩theorem clique_avoids (k : ℕ) (S : Finset (Fin m)) (hs : (graph m q A).IsNClique k S) :    S.card = k ∧ (SimpleGraph.cycleGraph m).IsIndepSet (↑S : Set (Fin m)) ∧      ∀ j, (S ∩ A j).card ≤ 1 := by  refine ⟨hs.card_eq, ?_, ?_⟩  · intro x hx y hy hxy hxy'    exact ((hs.isClique hx hy hxy).2.1) hxy'  · intro j    apply Finset.card_le_one.mpr    intro x hx y hy    by_contra hxy    have hxS := (Finset.mem_inter.mp hx).1    have hyS := (Finset.mem_inter.mp hy).1    have hxA := (Finset.mem_inter.mp hx).2    have hyA := (Finset.mem_inter.mp hy).2    exact ((hs.isClique hxS hyS hxy).2.2 j) ⟨hxA,hyA⟩end Inbox777Avoidtheorem op_193_avoidance_graph (m q k : ℕ) (A : Fin q → Finset (Fin m)) :    ∃ G : SimpleGraph (Fin m),      (∀ x y, G.Adj x y ↔ x ≠ y ∧ ¬ (SimpleGraph.cycleGraph m).Adj x y ∧        ∀ j, ¬(x ∈ A j ∧ y ∈ A j)) ∧      ∀ S : Finset (Fin m), G.IsNClique k S →        S.card = k ∧ (SimpleGraph.cycleGraph m).IsIndepSet (↑S : Set (Fin m)) ∧        ∀ j, (S ∩ A j).card ≤ 1 := by  exact ⟨Inbox777Avoid.graph m q A, (by intros; rfl), Inbox777Avoid.clique_avoids m q A k⟩
See it in the graphDiscuss this resultChallenge it