Deje $G$ un gráfico en $n$ vértices. Supongamos que cada vértice tiene más de 3 vecinos. Demostrar que se puede colorear los vértices de color rojo o azul en forma tal que cada vértice está conectado a un máximo de 1 vértices del mismo color.
He probado el siguiente enfoque: el Color de los vértices de forma aleatoria. A continuación, buscar en cada vértice, y si está conectado a más de uno de los vértices del mismo color, cambiar su color. Tenía la esperanza de que habrá algunos monovariant. La he considerado, que son muchas palabras para explicar, no de trabajo I consideró el número total de "off" elementos por vértice).
Mi segundo enfoque fue la construcción de la gráfica borde con borde, color a medida que avanza. Creo que tiene sentido dividir los vértices en cuatro particiones: $V_0$, $V_1$, $V_2$, e $V_3$ donde un vértice $v$ pertenece a $V_i$, 1$\leq i \leq 3$si $\deg(v)=i$. A continuación, vaya a través de cada vértice de $V_{1}$, la adición de cada borde y colorear cada par de vértices opuestos de colores, etc.... Algo a lo largo de esas líneas.
Puede alguien pensar que de un ingenioso/simple manera de demostrar esto? Porque, a pesar de que mi segundo enfoque funciona probablemente, requerirá de una tonelada de escritura técnica. Debe haber una manera más simple de pensar acerca de este problema.
