Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 59 / 4 / b

Let $N=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ be the number of independent undirected-edge bits; use unordered pairs $i<j$. The paper's common-center graph property means that all present edges share a vertex. Isolated vertices are allowed, and the empty graph satisfies the property. This convention matters in the count.

The empty graph contributes $+1$ to the alternating sum. The $N$ one-edge graphs contribute $-N$. A graph with at least two edges and a common center has a unique center, since two different edges have just that common endpoint. For a fixed center, its possible edge sets are subsets of the $n-1$ incident edges. Their contribution after removing sets of size zero and one isThese graphs are counted once for each of their unique centers. Thus the alternating count of common-center graphs isPart (a) gives $D({\mathrm{STAR}}_n)\ge N$, while querying all $N$ bits always suffices. ThereforeThe relevant input length is $N$, not the number $n$ of graph vertices.