Estoy tratando de demostrar que hay una forma de color (bordes) una gráfica de $K_{2t}$ $t$ colores por lo que no contiene ningún ciclos monocromáticos.
Pensé que para mostrar el gráfico como una Unión separada de los caminos de $t$ ($P_{2t-1}$) (cada ruta en diferentes colores, sin bordes mismo en cada uno de los caminos).
Este trabajo muy bien en teoría, lo único que no sé es si realmente puedo crear %#% caminos #% ($t$). Suena y parece buena pero ¿cómo puedo demostrar su derecho?
Gerry es el más elemental, pero también se puede utilizar el Tutte-Nash-Williams Teorema, que dice que un grafo $G$ es la unión de $t$ borde discontinuo de los bosques si y sólo si para cada subgrafo en $n'$ vértices y $m'$ bordes, la desigualdad de $m'\le tn' - t$ mantiene.
La declaración se ha demostrado es que el $K_{2t}$ es la unión de $t$ borde discontinuo de los bosques, por lo acabamos de comprobar la condición dada anteriormente. Hay $2t$ vértices y $t(2t-1)$ bordes, por lo que el deseado desigualdad se cumple la igualdad para el conjunto de la gráfica. Por otra parte, desde cualquier subgrafo inducido también es un grafo completo en menos de $2t$ vértices, vemos que el número de aristas es $\frac{1}{2}n'(n'-1) < t(2n'-1)$.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
