Question: Given $G(V,E)$, a $3$-regular $K_4$ free graph. Show that $G$ has a bipartite subgraph with at least $(7/9) m $ edges.
My attempt: Since $G$ is $3$-regular and $K_4$ free, it is $3$ colorable by Brook's Theorem. Let $S_1, S_2, S_3$ be a $3$ coloring partition of $V$. At least one must have $|S_i|\leq n/3$, say $S_1$. We let $X=S_2$ and $Y=S_3$. We add $u\in S_1$ to $Y$ if it has $2$-neighbours in $X$ and to $Y$ if it has 2 neighbours in $X$. In total, we get a bipartite graph with at least $m-n/3$ edges. We want $m-n/3 \geq 7m/9$ which is true for $m\geq 3n/2$. But $m=3n/2$ for $3$-regular graphs and so we are done.
Question: Is there a cleaner way to do this with the probabilistic method (i.e using 3 colourings right away without Brook's theorem).