How many labeled graphs on n vertices with k edges contain a
c-clique? Enumerate one block — the graphs holding a single fixed clique —
and weight each by the reciprocal of how many cliques it has. Symmetry collapses the outer sum to
that one term. The identity is Karp–Luby's; what is new is the orbit hypothesis that makes it
exactly evaluable instead of sampled. Exact tables for c ∈ {3,4},
n ≤ 8, with no published predecessor — and a negative result stated as a result:
the deficiency expansion converges only for k = o(√n), strictly inside the range
where the existing approximation is already tight.
[PDF][Abstract]
Classify each edge of a graph by how many of its endpoints it shares with another edge. Of the
C(n+2,2) possible counts, exactly five are unachievable for every n ≥ 3 — proved, not fitted.
A five-rule automaton computes the achievable set exactly, with no omissions and no spurious states.
[PDF][Code]
You may copy and redistribute any of them, in any medium or format, provided you credit the author,
link back to this page, and distribute the paper whole and unaltered. Commercial use, and the
distribution of modified or derived versions, require written permission — ask at
[email protected]. Quotation for review, comment,
scholarship, or teaching is unaffected by this license.
How to cite
@misc{klemm2026blockweighting,
author = {Brian Klemm},
title = {Counting Clique-Containing Graphs by Transitive Block Weighting},
year = {2026},
note = {https://brianklemm.com/publications/CliqueBlockWeighting.pdf}
}
@misc{klemm2026edgeattachment,
author = {Brian Klemm},
title = {Edge-Attachment Profiles of Graphs: An Exact Characterization},
year = {2026},
note = {https://brianklemm.com/publications/EdgeAttachmentProfiles.pdf}
}
@misc{klemm2025binarygroupedfactorial,
author = {Brian Klemm},
title = {Binary-Grouped Factorial},
year = {2025},
note = {https://brianklemm.com/publications/BinaryGroupedFactorial.pdf}
}