State-independent quantum contextuality and maximum nonlocality

Recently, Yu and Oh [Phys. Rev. Lett. 108, 030402 (2012)] have conjectured that the simplest set of vectors needed to prove state-independent contextuality on a qutrit requires 13 vectors. Here we first prove that a necessary and sufficient condition for a set of vectors in any dimension $d \ge 3$ to prove contextuality for a system prepared in a maximally mixed state is that the graph $G_C$ in which vertices represent vectors and edges link orthogonal ones has chromatic number $\chi (G_G)$ larger than $d$. Then, we prove Yu and Oh’s conjecture. Finally, we prove that any set satisfying $\chi (G_G)>d$ assisted with $d$-party maximum entanglement generates nonlocality which cannot be improved without violating the no-signalling principle. This shows that any set satisfying $\chi (G_G)>d$ is a valuable resource for quantum information processing.