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.


1 Answer 1


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
    Commented May 28, 2015 at 14:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .