Problem

Source: XIII International Festival of Young Mathematicians Sozopol 2024, Theme for 10-12 grade

Tags: combinatorics, graph theory



Consider a finite undirected graph in which each edge belongs to at most three cycles. Prove that its vertices can be colored with three colors so that any two vertices connected by an edge have different colors. (A cycle in a graph is a sequence of distinct vertices \( v_1, v_2, \ldots, v_k \), \( k \geq 3 \), such that \( v_i v_{i+1} \) is an edge for each \( i = 1, 2, \ldots, k \); we consider \( v_{k+1} = v_1 \). The edges \( v_i v_{i+1} \) belong to the cycle.)