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.

  • $\begingroup$ perfect! Thanks. $\endgroup$ – Omid B May 28 '15 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.