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 Letter, 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 [35M.-O. Renou, Phys. Rev. A 105, 022408 (2022)PLRAAN2469-992610.1103/PhysRevA.105.022408], where we introduce a second family of rigid strategies called token counting, leading to network nonlocality.