Q9 Matemática  (Baltic Way 2020)

Cada vértice $v$ e cada aresta $e$ de um grafo $G$ são atribuídos aos números $f(v)\in \{1,2\}$ e $f(e)\in \{1,2,3\}$, respectivamente. Seja $S(v)$ a soma dos números atribuídos às arestas incidentes a $v$ mais o número $f(v)$. Dizemos que uma atribuição $f$ é legal se $S(u)\ne S(v)$ para cada par $(u,v)$ de vértices adjacentes (isto é, conectados por uma aresta) em $G$. Prove que para cada gráfico existe uma atribuição legal.