Certificates for the common-center graph property ($C_1=\left(\genfrac{}{}{0ex}{}{n-1}{2}\right),C_0=3$)

For $n\ge 3$, 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,(\genfrac{}{}{0ex}{}{n-1}{2})\}=\Theta (n^2)$ for this property.