simple_graph_q_cone
If a finite simple graph $G$ is a cone, then $q(G) = 0$.
Statement
theorem simple_graph_q_cone {V : Type*} [Fintype V] (G : SimpleGraph V) (hcone : simple_graph_is_cone G) : simple_graph_q G = 0
- Source
- arXiv:2611.14430, Lemma 4.3
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- simple_graph_qThe invariant $q(G) = C_G(-1)$ of a finite simple graph $G$, obtained by evaluating its clique polynomial at $-1$.
- simple_graph_is_coneA simple graph is a cone if it is non-empty and has an apex (a universal vertex adjacent to all other vertices).
Read back from the Lean
For every finite type $V$ and every simple graph $G$ on $V$, if $G$ is a cone (meaning $V$ is nonempty and there exists a vertex in $V$ that is universal in $G$, i.e., adjacent to every other vertex), then simple_graph_q G = 0 (the clique polynomial of $G$ evaluated at $-1$ is zero).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To show that q(G) = 0 for a cone G, the polynomial evaluation q(G) = P_G(-1) is rewritten as an alternating sum ∑_{s ∈ F} (-1)^|s| over the collection F of all cliques of G. Because G has a universal vertex (apex) a, the operation of toggling whether a belongs to a clique defines a fixed-point-free involution on F. Each clique s is paired with a clique whose size differs by exactly 1, causing their contributions (-1)^|s| and (-1)^|g(s)| to cancel in pairs and yielding zero.
Adding a universal vertex to a clique or removing any vertex from a clique yields another clique.
Because a is universal, it is adjacent to every distinct vertex in s, so adding a preserves mutual adjacency and insert a s is a clique. Conversely, a subset of a clique is always a clique, so s \ {a} is a clique.
uses
Finset.coe_insert,SimpleGraph.isClique_insert.mpr,Finset.mem_of_mem_eraseprivate lemma simple_graph_q_cone_insert_isClique {V : Type*} [DecidableEq V] {G : SimpleGraph V} {a : V} (ha : G.IsUniversal a) {s : Finset V} (hs : G.IsClique (↑s : Set V)) : G.IsClique (↑(insert a s) : Set V) := by rw [Finset.coe_insert] exact SimpleGraph.isClique_insert.mpr ⟨hs, fun b hb hab => ha hab⟩ private lemma simple_graph_q_cone_erase_isClique {V : Type*} [DecidableEq V] {G : SimpleGraph V} {a : V} {s : Finset V} (hs : G.IsClique (↑s : Set V)) : G.IsClique (↑(s.erase a) : Set V) := hs.subset (fun _ hx => Finset.mem_of_mem_erase hx)
Consecutive powers of -1 sum to zero: (-1)^(m+1) + (-1)^m = 0 and (-1)^m + (-1)^(m+1) = 0. automation
Rewriting (-1)^(m+1) as (-1)^m * (-1), the sum simplifies to zero by ring arithmetic.
uses
pow_succprivate lemma simple_graph_q_cone_neg_one_pow_succ_add (m : ℕ) : (-1 : ℤ) ^ (m + 1) + (-1 : ℤ) ^ m = 0 := by rw [pow_succ]; ring private lemma simple_graph_q_cone_neg_one_pow_add_succ (m : ℕ) : (-1 : ℤ) ^ m + (-1 : ℤ) ^ (m + 1) = 0 := by rw [pow_succ]; ring
Toggling whether a belongs to a finset s is an involution on finsets.
By case analysis on whether a ∈ s: if a ∈ s, toggling removes a, and toggling again inserts a back, recovering s; if a ∉ s, toggling inserts a, and toggling again removes a, recovering s.
uses
if_pos,if_neg,Finset.notMem_erase,Finset.insert_erase,Finset.mem_insert_self,Finset.erase_insertprivate lemma simple_graph_q_cone_pair_involutive {V : Type*} [DecidableEq V] (a : V) (s : Finset V) : (if a ∈ (if a ∈ s then s.erase a else insert a s) then (if a ∈ s then s.erase a else insert a s).erase a else insert a (if a ∈ s then s.erase a else insert a s)) = s := by by_cases h : a ∈ s · rw [if_pos h, if_neg (Finset.notMem_erase a s), Finset.insert_erase h] · rw [if_neg h, if_pos (Finset.mem_insert_self a s), Finset.erase_insert h] /-- A cone has q = 0. -/
Unpacking the apex vertex a reduces the theorem to showing that the polynomial evaluation ∑_{t=0}^{|V|} c_t(G) (-1)^t equals 0.
From the cone hypothesis, we obtain an apex vertex a that is universal. Unfolding the definition of q(G) and the clique polynomial, evaluating at -1 distributes across the sum, products, constants, and powers, leaving the numerical sum of c_t(G) * (-1)^t.
uses
Polynomial.eval_finsetSum,Polynomial.eval_mul,Polynomial.eval_C,Polynomial.eval_pow,Polynomial.eval_Xtheorem simple_graph_q_cone {V : Type*} [Fintype V] (G : SimpleGraph V) (hcone : simple_graph_is_cone G) : simple_graph_q G = 0 := by classical obtain ⟨_, a, ha⟩ := hcone simp only [simple_graph_q, simple_graph_clique_polynomial] rw [Polynomial.eval_finsetSum] simp only [Polynomial.eval_mul, Polynomial.eval_C, Polynomial.eval_pow, Polynomial.eval_X] set F : Finset (Finset V) := Finset.univ.filter (fun s : Finset V => G.IsClique (↑s : Set V)) with hF
For each size t, the term c_t(G) * (-1)^t equals the sum of (-1)^|s| over all cliques s of size t.
Every clique s in G.cliqueFinset t has |s| = t, so (-1)^|s| is identically (-1)^t on this set. Summing this constant over G.cliqueFinset t multiplies it by the cardinality c_t(G).
uses
Finset.sum_congr,SimpleGraph.isNClique_iff,SimpleGraph.mem_cliqueFinset_iff.mp,Finset.sum_const,nsmul_eq_mulhave hterm : ∀ t, (∑ s ∈ G.cliqueFinset t, (-1 : ℤ) ^ s.card) = ((G.cliqueFinset t).card : ℤ) * (-1 : ℤ)^t := by intro t rw [Finset.sum_congr rfl (fun s hs => by rw [show s.card = t from (SimpleGraph.isNClique_iff G |>.mp (SimpleGraph.mem_cliqueFinset_iff.mp hs)).2])] rw [Finset.sum_const, nsmul_eq_mul]
The sets of cliques of different sizes are pairwise disjoint.
If a clique s belongs to both G.cliqueFinset i and G.cliqueFinset j, its cardinality |s| must equal both i and j, forcing i = j.
uses
Finset.pairwiseDisjoint_iff,Finset.mem_inter,SimpleGraph.isNClique_iff,SimpleGraph.mem_cliqueFinset_iff.mphave hdisj : ((Finset.range (Fintype.card V + 1) : Finset ℕ) : Set ℕ).PairwiseDisjoint (fun t => G.cliqueFinset t) := by rw [Finset.pairwiseDisjoint_iff] intro i _ j _ hne obtain ⟨s, hs⟩ := hne rw [Finset.mem_inter] at hs obtain ⟨hsi, hsj⟩ := hs have hi : s.card = i := (SimpleGraph.isNClique_iff G |>.mp (SimpleGraph.mem_cliqueFinset_iff.mp hsi)).2 have hj : s.card = j := (SimpleGraph.isNClique_iff G |>.mp (SimpleGraph.mem_cliqueFinset_iff.mp hsj)).2 exact hi.symm.trans hj
The union of the sets of cliques of size t over 0 ≤ t ≤ |V| is the set F of all cliques of G.
Every member of G.cliqueFinset t is a clique in G. Conversely, every clique s has cardinality |s| ≤ |V| < |V| + 1, so s belongs to the clique finset for its own size.
uses
Finset.mem_biUnion,Finset.mem_range,Finset.mem_filter,Finset.mem_univ,true_and,SimpleGraph.mem_cliqueFinset_iff.mp,Nat.lt_succ_of_le,Finset.card_le_univ,SimpleGraph.mem_cliqueFinset_iff.mpr,SimpleGraph.isNClique_iffhave hbiUnion : (Finset.range (Fintype.card V + 1)).biUnion (fun t => G.cliqueFinset t) = F := by ext s simp only [Finset.mem_biUnion, Finset.mem_range, hF, Finset.mem_filter, Finset.mem_univ, true_and] constructor · rintro ⟨t, _, ht⟩ exact (SimpleGraph.mem_cliqueFinset_iff.mp ht).isClique · intro hcl exact ⟨s.card, Nat.lt_succ_of_le (Finset.card_le_univ s), SimpleGraph.mem_cliqueFinset_iff.mpr ((SimpleGraph.isNClique_iff G).mpr ⟨hcl, rfl⟩)⟩
The polynomial sum ∑_{t=0}^{|V|} c_t(G) (-1)^t equals the single sum ∑_{s ∈ F} (-1)^|s| over all cliques of G.
By replacing each term with the sum over G.cliqueFinset t and using the pairwise disjointness of these finsets, the sum over t becomes the sum over their union, which equals F.
uses
Finset.sum_congr,Finset.sum_biUnionhave hEq1 : ∑ t ∈ Finset.range (Fintype.card V + 1), ((G.cliqueFinset t).card : ℤ) * (-1 : ℤ)^t = ∑ s ∈ F, (-1 : ℤ) ^ s.card := by calc ∑ t ∈ Finset.range (Fintype.card V + 1), ((G.cliqueFinset t).card : ℤ) * (-1 : ℤ)^t = ∑ t ∈ Finset.range (Fintype.card V + 1), ∑ s ∈ G.cliqueFinset t, (-1 : ℤ) ^ s.card := Finset.sum_congr rfl (fun t _ => (hterm t).symm) _ = ∑ s ∈ (Finset.range (Fintype.card V + 1)).biUnion (fun t => G.cliqueFinset t), (-1 : ℤ) ^ s.card := (Finset.sum_biUnion hdisj).symm _ = ∑ s ∈ F, (-1 : ℤ) ^ s.card := by rw [hbiUnion] rw [hEq1]
By the involution principle, it suffices to check four properties of the toggling map g, the first being that paired cliques have canceling signs: (-1)^|s| + (-1)^|g(s)| = 0.
We invoke Finset.sum_involution with the map g that toggles membership of the apex a. If a ∈ s, then g(s) = s \ {a} has size |s| - 1, and (-1)^((|s|-1)+1) + (-1)^(|s|-1) = 0. If a ∉ s, then g(s) = insert a s has size |s| + 1, and (-1)^|s| + (-1)^(|s|+1) = 0.
uses
Finset.sum_involution,if_pos,Finset.card_erase_add_one,simple_graph_q_cone_neg_one_pow_succ_add,if_neg,Finset.card_insert_of_notMem,simple_graph_q_cone_neg_one_pow_add_succrefine Finset.sum_involution (f := fun s : Finset V => (-1 : ℤ) ^ s.card) (g := fun s _ => if a ∈ s then s.erase a else insert a s) ?_ ?_ ?_ ?_ · intro s hs by_cases h : a ∈ s · rw [if_pos h] have hc : s.card = (s.erase a).card + 1 := (Finset.card_erase_add_one h).symm rw [hc] exact simple_graph_q_cone_neg_one_pow_succ_add _ · rw [if_neg h] rw [Finset.card_insert_of_notMem h] exact simple_graph_q_cone_neg_one_pow_add_succ _
The toggling map g has no fixed points on F.
If a ∈ s, then a ∉ s \ {a} = g(s), so g(s) cannot equal s. If a ∉ s, then a ∈ insert a s = g(s), so again g(s) cannot equal s.
uses
if_pos,Finset.notMem_erase,if_neg,Finset.mem_insert_self· intro s hs hfne hg by_cases h : a ∈ s · have hnot : a ∉ (if a ∈ s then s.erase a else insert a s) := by rw [if_pos h]; exact Finset.notMem_erase a s rw [hg] at hnot exact hnot h · have hmem : a ∈ (if a ∈ s then s.erase a else insert a s) := by rw [if_neg h]; exact Finset.mem_insert_self a s rw [hg] at hmem exact h hmem
The toggling map g preserves cliques: if s ∈ F, then g(s) ∈ F.
If a ∈ s, removing a from a clique yields a clique by simple_graph_q_cone_erase_isClique. If a ∉ s, inserting the universal vertex a yields a clique by simple_graph_q_cone_insert_isClique.
uses
Finset.mem_filter,Finset.mem_univ,true_and,if_pos,simple_graph_q_cone_erase_isClique,if_neg,simple_graph_q_cone_insert_isClique· intro s hs have hcl : G.IsClique (↑s : Set V) := by simpa only [hF, Finset.mem_filter, Finset.mem_univ, true_and] using hs rw [hF] simp only [Finset.mem_filter, Finset.mem_univ, true_and] by_cases h : a ∈ s · rw [if_pos h] exact simple_graph_q_cone_erase_isClique hcl · rw [if_neg h] exact simple_graph_q_cone_insert_isClique ha hcl
The toggling map g is an involution on F, completing the proof.
Toggling a twice returns the original clique s by simple_graph_q_cone_pair_involutive. By the involution principle, the terms in the sum cancel in pairs and the sum is zero.
uses
simple_graph_q_cone_pair_involutive· intro s hs exact simple_graph_q_cone_pair_involutive a s
Finset.coe_insert- The set coercion of insert a s equals the set insert of a into the set coercion of s.
SimpleGraph.isClique_insert.mpr- If s is a clique in G and a is adjacent to every distinct vertex in s, then s ∪ {a} is a clique.
Finset.mem_of_mem_erase- If an element belongs to s \ {a}, then it belongs to s.
pow_succ- The (n + 1)-th power of a equals a^n * a.
if_pos- If a proposition c holds, then `if c then t else e` equals t.
if_neg- If a proposition c does not hold, then `if c then t else e` equals e.
Finset.notMem_erase- The element a is not a member of s \ {a}.
Finset.insert_erase- If a ∈ s, inserting a into s \ {a} yields s.
Finset.mem_insert_self- The element a is always a member of insert a s.
Finset.erase_insert- If a ∉ s, removing a from insert a s yields s.
Polynomial.eval_finsetSum- Evaluating a finite sum of polynomials at x equals the sum of their individual evaluations at x.
Polynomial.eval_mul- Evaluating a product of polynomials at x equals the product of their evaluations at x.
Polynomial.eval_C- Evaluating a constant polynomial with value a at x yields a.
Polynomial.eval_pow- Evaluating the n-th power of a polynomial at x equals the n-th power of its evaluation at x.
Polynomial.eval_X- Evaluating the indeterminate X at x yields x.
Finset.sum_congr- Two sums over finite sets are equal if their index sets are equal and their summands agree on every element.
SimpleGraph.isNClique_iff- A finset s is an n-clique of G if and only if s is a clique and |s| = n.
SimpleGraph.mem_cliqueFinset_iff.mp- If s belongs to the finset of cliques of size n, then s is an n-clique.
Finset.sum_const- Summing a constant b over a finset s equals |s| • b.
nsmul_eq_mul- Scalar multiplication of a ring element by a natural number n equals multiplication by n.
Finset.pairwiseDisjoint_iff- A family of finsets is pairwise disjoint if and only if any two sets with a nonempty intersection have the same index.
Finset.mem_inter- An element belongs to the intersection of two finsets if and only if it belongs to both.
Finset.mem_biUnion- An element belongs to the union of a family of finsets indexed by s if and only if it belongs to some member of the family.
Finset.mem_range- A natural number a belongs to Finset.range n if and only if a < n.
Finset.mem_filter- An element belongs to s.filter p if and only if it belongs to s and satisfies p.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
true_and- True ∧ p is equivalent to p.
Nat.lt_succ_of_le- If n ≤ m, then n < m + 1.
Finset.card_le_univ- The cardinality of any finset of α is at most the total cardinality of α.
SimpleGraph.mem_cliqueFinset_iff.mpr- If s is an n-clique of G, then s belongs to the finset of cliques of size n.
Finset.sum_biUnion- If a family of finsets is pairwise disjoint, summing over their union equals summing over the family and then over each set.
Finset.sum_involution- If g is an involution on s pairing elements with opposite values under f and with no fixed points where f is non-zero, then the sum of f over s is zero.
Finset.card_erase_add_one- If a ∈ s, then |s \ {a}| + 1 = |s|.
simple_graph_q_cone_neg_one_pow_succ_add- For any natural number m, (-1)^(m+1) + (-1)^m = 0.
Finset.card_insert_of_notMem- If a ∉ s, then |insert a s| = |s| + 1.
simple_graph_q_cone_neg_one_pow_add_succ- For any natural number m, (-1)^m + (-1)^(m+1) = 0.
simple_graph_q_cone_erase_isClique- Removing any vertex from a clique yields a clique.
simple_graph_q_cone_insert_isClique- Adding a universal vertex to a clique yields a clique.
simple_graph_q_cone_pair_involutive- Toggling whether a belongs to s twice returns the original finset s.
- The algebraic cancellation (-1)^m * -1 + (-1)^m = 0 in the helper lemmas is dispatched by `ring`.
- The distribution of polynomial evaluation over the sum and monomials is handled by `simp`.
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.
private lemma simple_graph_q_cone_insert_isClique {V : Type*} [DecidableEq V] {G : SimpleGraph V} {a : V} (ha : G.IsUniversal a) {s : Finset V} (hs : G.IsClique (↑s : Set V)) : G.IsClique (↑(insert a s) : Set V) := by rw [Finset.coe_insert] exact SimpleGraph.isClique_insert.mpr ⟨hs, fun b hb hab => ha hab⟩private lemma simple_graph_q_cone_erase_isClique {V : Type*} [DecidableEq V] {G : SimpleGraph V} {a : V} {s : Finset V} (hs : G.IsClique (↑s : Set V)) : G.IsClique (↑(s.erase a) : Set V) := hs.subset (fun _ hx => Finset.mem_of_mem_erase hx)private lemma simple_graph_q_cone_neg_one_pow_succ_add (m : ℕ) : (-1 : ℤ) ^ (m + 1) + (-1 : ℤ) ^ m = 0 := by rw [pow_succ]; ringprivate lemma simple_graph_q_cone_neg_one_pow_add_succ (m : ℕ) : (-1 : ℤ) ^ m + (-1 : ℤ) ^ (m + 1) = 0 := by rw [pow_succ]; ringprivate lemma simple_graph_q_cone_pair_involutive {V : Type*} [DecidableEq V] (a : V) (s : Finset V) : (if a ∈ (if a ∈ s then s.erase a else insert a s) then (if a ∈ s then s.erase a else insert a s).erase a else insert a (if a ∈ s then s.erase a else insert a s)) = s := by by_cases h : a ∈ s · rw [if_pos h, if_neg (Finset.notMem_erase a s), Finset.insert_erase h] · rw [if_neg h, if_pos (Finset.mem_insert_self a s), Finset.erase_insert h]/-- A cone has q = 0. -/theorem simple_graph_q_cone {V : Type*} [Fintype V] (G : SimpleGraph V) (hcone : simple_graph_is_cone G) : simple_graph_q G = 0 := by classical obtain ⟨_, a, ha⟩ := hcone simp only [simple_graph_q, simple_graph_clique_polynomial] rw [Polynomial.eval_finsetSum] simp only [Polynomial.eval_mul, Polynomial.eval_C, Polynomial.eval_pow, Polynomial.eval_X] set F : Finset (Finset V) := Finset.univ.filter (fun s : Finset V => G.IsClique (↑s : Set V)) with hF have hterm : ∀ t, (∑ s ∈ G.cliqueFinset t, (-1 : ℤ) ^ s.card) = ((G.cliqueFinset t).card : ℤ) * (-1 : ℤ)^t := by intro t rw [Finset.sum_congr rfl (fun s hs => by rw [show s.card = t from (SimpleGraph.isNClique_iff G |>.mp (SimpleGraph.mem_cliqueFinset_iff.mp hs)).2])] rw [Finset.sum_const, nsmul_eq_mul] have hdisj : ((Finset.range (Fintype.card V + 1) : Finset ℕ) : Set ℕ).PairwiseDisjoint (fun t => G.cliqueFinset t) := by rw [Finset.pairwiseDisjoint_iff] intro i _ j _ hne obtain ⟨s, hs⟩ := hne rw [Finset.mem_inter] at hs obtain ⟨hsi, hsj⟩ := hs have hi : s.card = i := (SimpleGraph.isNClique_iff G |>.mp (SimpleGraph.mem_cliqueFinset_iff.mp hsi)).2 have hj : s.card = j := (SimpleGraph.isNClique_iff G |>.mp (SimpleGraph.mem_cliqueFinset_iff.mp hsj)).2 exact hi.symm.trans hj have hbiUnion : (Finset.range (Fintype.card V + 1)).biUnion (fun t => G.cliqueFinset t) = F := by ext s simp only [Finset.mem_biUnion, Finset.mem_range, hF, Finset.mem_filter, Finset.mem_univ, true_and] constructor · rintro ⟨t, _, ht⟩ exact (SimpleGraph.mem_cliqueFinset_iff.mp ht).isClique · intro hcl exact ⟨s.card, Nat.lt_succ_of_le (Finset.card_le_univ s), SimpleGraph.mem_cliqueFinset_iff.mpr ((SimpleGraph.isNClique_iff G).mpr ⟨hcl, rfl⟩)⟩ have hEq1 : ∑ t ∈ Finset.range (Fintype.card V + 1), ((G.cliqueFinset t).card : ℤ) * (-1 : ℤ)^t = ∑ s ∈ F, (-1 : ℤ) ^ s.card := by calc ∑ t ∈ Finset.range (Fintype.card V + 1), ((G.cliqueFinset t).card : ℤ) * (-1 : ℤ)^t = ∑ t ∈ Finset.range (Fintype.card V + 1), ∑ s ∈ G.cliqueFinset t, (-1 : ℤ) ^ s.card := Finset.sum_congr rfl (fun t _ => (hterm t).symm) _ = ∑ s ∈ (Finset.range (Fintype.card V + 1)).biUnion (fun t => G.cliqueFinset t), (-1 : ℤ) ^ s.card := (Finset.sum_biUnion hdisj).symm _ = ∑ s ∈ F, (-1 : ℤ) ^ s.card := by rw [hbiUnion] rw [hEq1] refine Finset.sum_involution (f := fun s : Finset V => (-1 : ℤ) ^ s.card) (g := fun s _ => if a ∈ s then s.erase a else insert a s) ?_ ?_ ?_ ?_ · intro s hs by_cases h : a ∈ s · rw [if_pos h] have hc : s.card = (s.erase a).card + 1 := (Finset.card_erase_add_one h).symm rw [hc] exact simple_graph_q_cone_neg_one_pow_succ_add _ · rw [if_neg h] rw [Finset.card_insert_of_notMem h] exact simple_graph_q_cone_neg_one_pow_add_succ _ · intro s hs hfne hg by_cases h : a ∈ s · have hnot : a ∉ (if a ∈ s then s.erase a else insert a s) := by rw [if_pos h]; exact Finset.notMem_erase a s rw [hg] at hnot exact hnot h · have hmem : a ∈ (if a ∈ s then s.erase a else insert a s) := by rw [if_neg h]; exact Finset.mem_insert_self a s rw [hg] at hmem exact h hmem · intro s hs have hcl : G.IsClique (↑s : Set V) := by simpa only [hF, Finset.mem_filter, Finset.mem_univ, true_and] using hs rw [hF] simp only [Finset.mem_filter, Finset.mem_univ, true_and] by_cases h : a ∈ s · rw [if_pos h] exact simple_graph_q_cone_erase_isClique hcl · rw [if_neg h] exact simple_graph_q_cone_insert_isClique ha hcl · intro s hs exact simple_graph_q_cone_pair_involutive a s