Demuestre que todo grafo cúbico libre de K4 G tiene un subgrafo bipartito con al menos m-n/3 aristas

Question

Supongamos que $G$ es un cúbico $K_4$ -Gráfico libre con $m$ bordes y $n$ vértices, demostrar que existe un subgrafo bipartito de $G$ con al menos $m-\frac{n}{3}$ bordes.

Sólo puedo demostrar que podemos encontrar un subgrafo bipartito de $G$ con al menos $m-\frac{n}{2}$ aristas. La prueba es mediante un algoritmo codicioso. Primero elegimos un subgrafo bipartito arbitrario. cada vez que elegimos un vértice que tiene como máximo un vecino en otra partición. Si movemos este vértice a otra partición, el número de aristas del grafo bipartito se incrementa en al menos uno. este algoritmo termina cuando para cada vértice, tiene al menos dos vecinos en otra partición. así que en cada partición podemos agrupar los vértices en pares, de manera que cada uno sea vecino de otro en el grafo principal. el número total de pares es como máximo $\frac{n}{2}$ . por lo que la afirmación queda demostrada.

Answer 1

Por Teorema de Brooks el gráfico es $3$ -colable. Por lo tanto, podemos elegir un $3$ -de la gráfica, con los colores de los vértices rojo, verde y azul, de manera que haya $\leq n/3$ vértices azules.

Para cada vértice azul $v$ : Si tiene $\leq 1$ vecinos rojos, recolor $v$ rojo, y eliminar el borde rojo-rojo si introducimos uno. En caso contrario, $v$ tiene $\leq 1$ vecinos verdes, por lo que lo volvemos a colorear de verde, y eliminamos el borde verde a verde si introducimos uno.

Al final, tenemos un $2$ -subgrafo coloreado con $\geq m-n/3$ bordes.