Mallas y colores

Supongamos que nos plantean el siguiente problema: tenemos una malla de 66 nodos y cada nodo está conectado con los otros con un segmento que puede ser de uno de cuatro colores diferentes, demostrar que al menos hay un conjunto de tres nodos que están conectados entre sí por el mismo color.
El problema parece imposible a primera vista pero partiendo de un caso más simple se puede ver que sí existe solución, veamos el problema planteado originalmente:
http://santiprofemates.wordpress.com/2012/02/16/desafio-409-los-mensajeros/

Caso A: tenemos 6 nodos y 2 colores

De cada nodo salen 5 líneas, 3 al menos han de ser del mismo color. Esas líneas van a tres nodos si alguna de las conexiones que conectan esos tres nodos fuera del mismo color tendríamos un triángulo monocolor. Pero en caso contrario tendríamos que las conexiones entre esos tres nodos serían del otro color formando un triángulo monocolor.

Hemos pintado las conexiones del nodo 0 a los nodos 1,2,3 de color rojo y a los nodos 4 y 5 de color azul. Ahora miramos las conexiones entre los nodos 1,2,3 que están provisionalmente en negro y debemos ponerlas en rojo o azul. Si la conexión 1-2 la ponemos en rojo el triángulo 0,1,2 será rojo en su conjunto, luego tenemos que poner 1-2 en azul. Lo mismo ocurre para la conexión 2-3 y para 1-3. Luego nos sale que el triángulo 1,2,3 es azul todo él o sea monocolor.

Caso B: 17 nodos y tres colores

De cada nodo salen 16 líneas, 6 al menos han de ser del mismo color. Esas líneas van a seis nodos si alguna de las conexiones que conectan  esos seis nodos fuera del mismo color tendríamos un triángulo monocolor. Pero en caso contrario tendríamos seis nodos conectados con dos colores diferentes que es el caso anterior A y que sabemos que ha de producir al menos un triángulo monocolor.

Caso C: 66 nodos con cuatro colores.

De cada nodo salen 65 líneas, 17 al menos han de ser del mismo color. Esas líneas van a 17 nodos si alguna de las conexiones que conectan esos 17 nodos fuera del mismo color tendríamos un triángulo monocolor. Pero en caso contrario tendríamos 17 nodos conectados con tres colores diferentes que es el caso anterior B y que sabemos que ha de producir al menos un triángulo monocolor.

Como se ve la generalización es muy sencilla y los siguientes valores para 5,6,7,8... colores sería: 327,1958,13701,109602... nodos

http://en.wikipedia.org/wiki/Ramsey%27s_theorem