Forbidden graph minors, Arkhipov's theorem, and linear system games

NEW

Problem: Reconstructed statement: for a finite graph $G=(V,E)$ and $b\in\mathbb F_2^V$, let $\mathcal G(G,b)$ be the linear-system game for the incidence equations

$$\sum_{e\ni v} x_e=b_v\pmod 2\qquad(v\in V).$$

The conjecture says: all perfect strategies of $\mathcal G(G,b)$ have classical correlation matrices iff $\sum_v b_v=0\pmod2$.

Result: The literal statement is false.

Take $G=K_2$, with vertices $u,v$ and unique edge $e$. Let $b_u=0,\ b_v=1$. Then $b$ has odd parity. The two equations are

$$x_e=0,\qquad x_e=1,$$

so no perfect strategy exists: Alice’s answer at $u$ forces Bob’s answer to $e$ to be $0$ with probability $1$, while Alice’s answer at $v$ forces Bob’s same answer to $e$ to be $1$ with probability $1$, impossible.

Hence the assertion “all perfect strategies have classical correlation matrices” is vacuously true, while $b$ is odd. This falsifies the stated “if and only if”.

The defect is a missing non-vacuity hypothesis, e.g. requiring that $\mathcal G(G,b)$ actually have a perfect strategy, or restricting to a setting such as connected nonplanar $G$ where odd-parity games have perfect quantum strategies.

Moreover, under the usual full-correlation-matrix convention, even that natural repair is not enough. Let $G$ be three triangles connected by bridges, with a $K_5$ attached by another bridge, and take $b\equiv0$. Use a maximally entangled qubit pair and assign to the three triangles Pauli observables $X_1,X_2,X_3$ with pairwise normalized traces $\operatorname{tr}(X_iX_j)/2=-1/2$, assigning identity to all bridge and $K_5$ edges. This gives a perfect strategy. The $3\times3$ sub-correlation matrix has diagonal $1$ and off-diagonal $-1/2$. No classical perfect strategy can realize this, since for signs $S_1,S_2,S_3$,

$$S_1S_2+S_1S_3+S_2S_3\ge -1,$$

but the constructed correlations give expectation $-3/2$.

Thus the conjecture, as stated, is rigorously disproved.

Citation: No external citation needed; the counterexamples are elementary.