Olimpiada China de Selección de Equipos (TST) 1993 Problema 3

3 Se da un grafo $G=(V,E)$. Si se requieren al menos $n$ colores para pintar sus vértices de modo que entre cualesquiera dos vértices del mismo color no haya ninguna arista, entonces se dice que este grafo es ''$n-$ coloreado''. Demuestre que para todo $n \in \mathbb{N}$ existe un grafo $n-$coloreado sin triángulos.

0

0

Kevin

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados