Certificates for the common-center graph property
= Certificates for the common-center graph property
{title2=$C_1=\binom{n-1}{2},\quad C_0=3$}
For $n\geq3$, a full <star graph> requires every nonincident edge to be certified absent, and fixing those bits suffices. Rejection is certified by at most three present edges with empty common intersection; a triangle needs all three. Hence <query certificate complexity> is $\max\{3,\binom{n-1}{2}\}=\Theta(n^2)$ for this property.