  Bell's theorem shows that correlations created by a single entangled quantum
state cannot be reproduced classically. Such correlations are called Nonlocal.
They are the elementary manifestation of a broader phenomenon called Network
Nonlocality, where several entangled states shared in a network create Network
Nonlocal correlations. In this paper, we provide the first class of strategies
producing nonlocal correlations in generic networks. In these strategies,
called Color-Matching (CM), any source takes a color at random or in
superposition, where the colors are labels for a basis of the associated
Hilbert space. A party (besides other things) checks if the color of
neighboring sources match. We show that in a large class of networks without
input, well-chosen quantum CM strategies result in nonlocal correlations that
cannot be produced classically. For our construction, we introduce the graph
theoretical concept of rigidity of classical strategies in networks, and using
the Finner inequality, establish a deep connection between network nonlocality
and graph theory. In particular, we establish a link between CM strategies and
the graph coloring problem. This work is extended in a longer paper, Network
Nonlocality via Rigidity of Token-Counting and Color-Matching, where we
introduce a second family of rigid strategies called Token-Counting, leading to
network nonlocality.
