 Certificates for the common-center graph property

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.