Brian Klemm // Independent researcher // August 2026
[PDF, 29 pages]
Let C(n,c,k) be the set of labeled graphs on n vertices with exactly
k edges containing at least one c-clique. This paper gives an exact
evaluation of |C(n,c,k)| that enumerates a single block — the
k-edge graphs in which one fixed c-clique is present — rather than the full
space of C(C(n,2),k) graphs. Writing h_r for the number of block graphs
containing exactly r cliques in total, |C| = C(n,c) · Σ h_r/r.
The underlying identity is not new: it is the union-of-sets coverage identity of Karp and Luby, which
expresses the size of a union as a sum of reciprocal-multiplicity weights. The contribution here is to
isolate the structural hypothesis that makes it exactly evaluable. An orbit-collapse proposition — if a
group acts on the index set of the family compatibly with the sets themselves, the outer sum reduces to
one term per orbit, weighted by orbit size — together with the observation that Sym(n)
acting on the c-subsets of [n] gives a single orbit, turns an identity
normally estimated by Monte Carlo into one computable exactly by finite enumeration. Two consequences
follow at no cost: a single block determines not just |C| but the entire distribution of
clique counts; and a second application, to monochromatic cliques in two-colourings, needs the orbit
form essentially, having two orbits whose contributions differ.
The cost accounting is deliberately unfavourable to the method. The saving over exhaustive enumeration
is a factor of Π (N−i)/(k−i), not the C(n,c) one might expect; the method
is not a complexity-class improvement; sampling the same identity yields an approximation scheme
polynomial in n and is preferable wherever exactness is not required; and enumerating the
K_c-free graphs and subtracting is cheaper in an identifiable regime, which the paper
measures and reports rather than omits.
The case for exact evaluation is made computationally: 156 triples (n,c,k) agreeing with
independent exhaustive enumeration and 4 not attempted, with no disagreements; agreement with two
further independent implementations; complete integer tables for c ∈ {3,4} and
n ≤ 8, for which no published predecessor was found; and two external checks, in which
the saturation threshold recovered by the counter reproduces the Turán number ex(n,K_c)
and the two-colour count reproduces R(3,3) = 6. All arithmetic is performed over the
rationals; no floating-point operation occurs in the counting path.
Finally, the enumeration is removed in the regime where that is possible. For fixed c and
k, decomposition by non-isolated vertex set makes H_r(n) a polynomial in
n. Regrading the same decomposition by deficiency 2k − v, in the
manner of Wright, restores a finite table at every order once k grows with n,
and yields an exact expansion whose truncation at order D is a certified lower bound, with
relative error measured to fall as (k²/n)^(D+1). The exact leading ratio
2k(k−1)/(n−2k+1) identifies the expansion parameter as k²/n and so confines
convergence to k = o(√n) — narrower than the o(n) regime of the
Chen–Stein approximation of DeSalvo and Rombach, and inside it. That limitation is reported as the
paper's principal negative result rather than as future work.
|C(n,c,k)| for c ∈ {3,4} and
n ≤ 8.k, and an exact statement
of how far short of the asymptotic literature it falls.
The K_c-free arrays refined by edge count, and their complement, are being submitted to
the OEIS. Row sums of the
c = 3 array reproduce
A213434; row lengths
reproduce the Turán numbers. Every term has been verified by two independent enumerations.
@misc{klemm2026blockweighting,
author = {Brian Klemm},
title = {Counting Clique-Containing Graphs by Transitive Block Weighting},
year = {2026},
note = {https://brianklemm.com/publications/CliqueBlockWeighting.pdf}
}© 2026 Brian Klemm. This paper is licensed under Creative Commons Attribution–NonCommercial–NoDerivatives 4.0 International (CC BY-NC-ND 4.0): share it anywhere you like, whole and unaltered, with credit to the author. Commercial use and derivative versions require written permission — [email protected]. Quotation for review, comment, scholarship, or teaching is unaffected by this license.