# Show that every cubic K4-free graph G has a bipartite subgraph with at least m-n/3 edges

Suppose $G$ is a cubic $K_4$-free Graph with $m$ edges and $n$ vertices, prove that there exists a bipartite subgraph of $G$ with at least $m-\frac{n}{3}$ edges.

I can only prove we can find a bipartite subgraph of $G$ with at least $m-\frac{n}{2}$ edges. The proof is by greedy algorithm.First we choose an arbitrary bipartite subgraph. every time we pick a vertex that has at most one neighbor in another partition. If we move this vertex to another partition , the number of edges of bipartite graph increases by at least one. this algorithm ends whenever for every vertex , it has at least two neighbors in another partition. so in each partition we can group vertices in pairs , so that each are neighbors of each other in main graph. the total number of pairs are at most $\frac{n}{2}$ . so the assertion is proved.

By Brooks's Theorem, the graph is $3$-colorable. We can thus pick a $3$-coloring of the graph, with vertex colors red, green, and blue, such that there are $\leq n/3$ blue vertices.
For each blue vertex $v$: If it has $\leq 1$ red neighbors, recolor $v$ red, and delete the red-to-red edge if we introduce one. Otherwise, $v$ has $\leq 1$ green neighbors, so we recolor it green, and delete the green-to-green edge if we introduce one.
In the end, we have a $2$-colored subgraph with $\geq m-n/3$ edges.