Teorema de los cuatro colores y teorema de Kuratowski en matemáticas discretas

Gráfico plano:
si un gráfico se puede dibujar en el plano sin cruzarse, se dice que es plano.
La coloración de un gráfico simple es la asignación de color a cada vértice del gráfico de modo que no se asigne el mismo color a dos vértices adyacentes.

Gráficos bipartitos: un gráfico bipartito, también conocido como bigráfico 
, es un conjunto de vértices de gráficos que se ha dividido en dos conjuntos distintos, sin vértices de gráficos en el mismo conjunto que sean adyacentes. Un gráfico bipartito es un gráfico k-partido con k=2 como instancia particular. 

Número cromático: 
el número mínimo de colores necesarios para pintar un gráfico G se denomina número cromático de G y se denota por – μ (G)

Regiones adyacentes:
una asignación de colores a las regiones de un mapa de modo que las regiones adyacentes tengan colores diferentes.
Un mapa ‘M’ es n – coloreable si existe una coloración de M que usa ‘n’ colores.

Teorema de los cuatro colores:
en 1852, Francis Guthrie, alumno de Augustus De Morgan, un notable matemático y lógico británico, propuso el problema de los cuatro colores. Definió el problema en términos de mapas que cumplen requisitos específicos, como no tener agujeros y conectar cada región (por ejemplo, país o estado) para que ninguna región exista en dos o más secciones no contiguas. 
Guthrie afirmó que con tales mapas, no se requerirían más de cuatro colores para colorear el mapa, de modo que no haya dos partes adyacentes del mismo color. 
Si las regiones de un Mapa M están coloreadas de modo que las regiones adyacentes sean diferentes, entonces no se requieren más de 4 colores.
Cada gráfico plano tiene 4 colores (coloreado de vértices), pero cuando un triángulo es un gráfico o subgráfico, solo necesitamos 3 colores.

Los matemáticos habían estado intentando durante años llegar a una demostración sofisticada (del teorema de los cuatro colores) similar al Teorema de los seis colores o al Teorema de los cinco colores, y usar el método de la fuerza bruta casi parecía piratear el proceso. 
Cada gráfico plano se puede colorear de cuatro maneras diferentes.
Los vértices y las aristas se encuentran en los gráficos. Queremos que los vértices/regiones adyacentes sean de diferentes colores.

¿Cómo colorear?
Tome cualquier mapa y divídalo en un conjunto de regiones conectadas: R ₁ ,R ₂ … R _n con límites continuos.
Debe haber alguna forma de asignar cada región R _i  -> en el conjunto {R, G, B, Y} , tal que si dos regiones R _i y R _j se «tocan» (es decir, comparten una longitud de límite distinta de cero entre ellos), deben recibir diferentes colores. 
Ejemplo: 
1. El mapa de cuatro colores se muestra a continuación: 

Aquí, como puede ver, cada región que toca otra región tiene un color diferente al de la que toca y requerimos un total de un máximo de cuatro colores para colorear este mapa: rojo, verde, azul y amarillo.

2. La transformación de un Mapa G sin color en un Mapa coloreado se muestra a continuación:

Aquí puede ver que cada región que toca otra región tiene un color diferente al que toca y requerimos un total de cuatro colores como máximo para colorear este mapa: rojo, verde, azul y amarillo.

3. La transformación de un Mapa H sin color en un Mapa coloreado se muestra a continuación:

Aquí también puede ver que cada región que toca otra región tiene un color diferente al que toca y requerimos un total de un máximo de cuatro colores para colorear este mapa: rojo, verde, azul y amarillo.

Teorema de Kuratowski:
Kuratowski estableció el teorema que establece una condición necesaria y suficiente para la planaridad en 1930. El teorema establece que:

"If G is non planar if and only if G contains a sub-graph that is a subdivision
 of either K3,3 or K5."

Para probar este teorema, analizaremos algunas definiciones y nos aseguraremos de que tanto K3,3 como K5 no sean planos. Echemos un vistazo a K _3,3 . 

Proposición 1 – K _3,3 no es plana.
Demostración: 
Ahora, lo probaremos por contradicción.  
Decir, por el contrario, que K _3,3 es plano. Entonces hay una incrustación plana de K _3,3 que satisface:
Entonces, por la fórmula de Euler: v − e + f = 2 , donde v = vértices totales, e = número de aristas, f = caras totales.
 

En la figura (a), el gráfico bipartito: v= 6 y e= 9. 

Como K _3,3 es bipartito, no hay 3 ciclos en él (puede haber ciclos impares).  
Por tanto, cada cara del empotramiento debe estar delimitada por al menos 4 aristas desde K _3,3.  
Además, cada borde se cuenta dos veces entre los límites de las caras.  
Por lo tanto, debemos tener: f ≤2 *e/4 
⇒ f ≤ e/2  
⇒ f ≤ 4.5.
Ahora pon estos datos en la fórmula de Euler: obtenemos: 2 =v−e+f
⇒ 2 ≤ 6−9 + 4.5 
⇒ 2 ≤ 1.5, lo cual es obviamente falso.  
Entonces, podemos decir que K _3,3 es un gráfico no plano.

Proposición 2 – K5 no es plana.
Prueba: 
Todo gráfico plano debe seguir: e ≤ 3v − 6 (corolario de la fórmula de Euler)
Para el gráfico (b) en el diagrama anterior, e = 10 y v = 5. 
LHS : e = 10
RHS : 3*v – 6 = 15 – 6 = 9
⇒ 10 ≤ 9, lo cual no es cierto.
Entonces, podemos decir que K ₅ es un gráfico no plano.

Ejemplo:
1. Demostrar que: Los subgráficos de un gráfico plano son todos planos.
Prueba: 
Sea G el gráfico y P su subgráfico.
Existe una incrustación plana de G, si G es plana. En la incrustación plana de G, podemos ubicar los vértices y las aristas de cada subgrafo P de G.
Así es como se crea una incrustación plana de P.

2. Las subdivisiones de un gráfico no plano son todas no planas.
Demostración: 
Suponga que para G, existe una incrustación plana de su subdivisión, P. 
Adquirimos una incrustación plana de G y encontramos G plana cuando eliminamos los vértices formados en las subdivisiones de borde y reconstruimos el borde original (sin afectar la forma y la posición del camino).
Como resultado, si G no es plano, también lo es toda subdivisión (P) de G.