The Quad-$C_5$ Graph: Maximum Contextuality Gap on Eight Vertices

Abstract

We perform an exhaustive semidefinite-programming search over all 11{,}117 connected non-isomorphic simple graphs on eight vertices to maximize the quantum contextuality gap $Δ(G)=\vartheta(G)-α(G)$, where $\vartheta(G)$ is the Lovász theta function and $α(G)$ is the independence number of the exclusion graph $G$ within the Cabello--Severini--Winter framework for projective measurements. A previously uncharacterized graph on $n=8$ vertices and $m=10$ edges, which we name the Quad-$C_5$ graph (graph6 code: \texttt{GCQb`o}), achieves $Δ=0.46784$, surpassing the Wagner graph $W$ ($Δ\approx0.414$, $m=12$) with two fewer edges. We determine numerically, via the PSLQ integer-relation algorithm at 50-digit precision, that Quad-$C_5$ is a \emph{qutrit} contextuality witness with $η_3=1+\sqrt{5}$ (minimal polynomial $x^2-2x-4=0$), while numerical evidence indicates the Wagner graph requires a four-dimensional (two-qubit) Hilbert space. The graph contains four mutually overlapping induced five-cycles, and its adjacency spectrum is dominated by golden-ratio eigenvalues, tracing the contextuality advantage algebraically to the KCBS pentagon. Under depolarizing noise, Quad-$C_5$ at $d=3$ shares the critical visibility $v^*=1/(3\sqrt{5}-5)\approx0.585$ of the KCBS witness -- an analytically provable coincidence arising from a uniform shift of the graph parameters -- while at $d=4$ it strictly surpasses the Wagner graph in noise robustness.