Q20 Matemática  (KoMaL A Problems 2022)

Seja $n>1$ um dado inteiro. Seja $G$ um grafo simples finito com a propriedade de que cada uma de suas arestas está contida em no máximo $n$ ciclos. Prove que o número cromático do grafo é no máximo $n+1$.