Demostrar que todo grafo 3-regular (simple) tiene Vertex bipartition s.t. each vertex has at most deg=1 within partition class

Question

Dada una $3$ -grafo regular $G$ quiero demostrar que puedo dividir el conjunto de vértices en conjuntos $A,B$ de forma que cada vértice tenga como máximo un vecino dentro de su clase de partición.

Se me han ocurrido dos ideas, pero no puedo llevar ninguna a casa: Una usando coloración de aristas, otra usando el criterio de ciclo impar para grafos bipartitos. En cuanto a la coloración de aristas, pensé que si podía encontrar un $3$ - coloración de los bordes, tal vez pueda construir mis conjuntos $A,B$ como desee. Pero entonces leí sobre la $3$ -regular de Petersen que no es $3$ -borde coloreable... Con respecto a los ciclos impar, pensé que tal vez podría romper los ciclos impar para crear un gráfico bipartito de modo que la adición de los bordes eliminados de nuevo todavía añade a lo sumo una "interna" (dentro de $A$ ou $B$ ) borde. Pero como he dicho, hasta ahora no he llegado a ninguna parte...

Answer 1

Por el teorema de Brooks, a menos que $G$ es el gráfico tetraédrico $K_4$ su número cromático $\chi(G)$ es como máximo $3$ . Ahora toma una coloración adecuada de $G$ donde los vértices están coloreados en azul, blanco y rojo.

Si un vértice $v$ es rojo (azul) pero

• tiene al menos dos vecinos blancos
• los vecinos de esos vecinos a distancia 2 de $v$ son todos azules (rojos)

a continuación, volver a colorear $v$ blanco y sus vecinos blancos rojos (azules):

Repite el proceso hasta que no se puedan recolorear más vértices de esta forma; el número de vértices blancos disminuye estrictamente con cada recoloreado, por lo que este proceso debe terminar.

La bipartición deseada en conjuntos de vértices $U$ y $V$ es la siguiente:

• Todos los vértices azules están en $U$
• Todos los vértices rojos están en $V$
• Un vértice blanco está en la partición correspondiente al color minoritario entre sus vecinos (es decir, en $U$ si es adyacente a cero o uno de los vértices azules)

Pour $K_4$ se puede obtener una bipartición admisible colocando dos vértices cualesquiera en $U$ y los otros dos en $V$ .

Answer 2

Elija la bipartición con el más bordes que cruzan de una parte a otra.

Si hubiera un vértice con al menos $2$ vecinos en la misma parte, y por tanto como máximo $1$ vecino en la parte opuesta, podrías mover ese vértice al otro lado y aumentar el número de aristas de cruce. Pero esto es imposible, ya que empezamos con la bipartición que tenía más aristas de cruce.

Por tanto, cada vértice tiene como máximo $1$ vecino en la misma parte.