Necesito descomponer cualquier grafo Regular conectado en ciclos Hamiltonianos y emparejamientos Perfectos. ¿Existe algún teorema que lo garantice o algún contraejemplo? Si existe tal teorema, ¿existe algún algoritmo para encontrar descomposiciones?
Respuesta
¿Demasiados anuncios?
El ( $3$ -regular) de Petersen es un contraejemplo. Primero demostramos que no se puede colorear correctamente con tres colores. Es decir, no podemos colorear las aristas con tres colores de modo que no haya dos aristas del mismo color que compartan un vértice común. 
No hay forma de colorear tres aristas del pentágono exterior del mismo color sin que dos de ellas se crucen, así que debemos tener dos pares de aristas del mismo color y la quinta arista de un tercer color. WLOG podemos colorear las aristas exteriores como se muestra. Esto obliga a que las aristas que van del pentágono exterior a la estrella interior se coloreen como se muestra. Ahora la arista $57$ interseca una arista azul y una arista roja, por lo que debe ser de color verde. (Veo que la arista $27$ parece más rosa que rojo, pero eso es sólo un error. Considéralo rojo). Del mismo modo, el borde $79$ debe ser de color verde. Pero estas aristas se encuentran en el vértice $7$ por lo que una coloración adecuada de los bordes no es posible con tres colores.
Ahora podemos demostrar que el gráfico de Petersen no es hamiltoniano. Si hay un ciclo de Hamilton, colorea sus aristas alternativamente en rojo y verde. Entonces podemos colorear las aristas restantes de azul para obtener una coloración de aristas adecuada con tres colores, que sabemos que es imposible.
Como el grafo de Petersen no es hamiltoniano, cualquier descomposición del tipo deseado sólo puede ser una partición en tres emparejamientos perfectos. Si tenemos una partición de este tipo, podemos colorear cada arista según el emparejamiento en el que aparezca. Dado que cada vértice aparece una vez en cada partición, se obtiene un color de arista propio con tres colores, lo cual es imposible.
