Planar graph and bipartite sub graph

59 Views Asked by At

Trying to figure out a proof of the following:

Let $G=(V,E)$ be a planar graph. Prove that $G$ contains a bipartite sub-graph with at least $\dfrac23|E|$ edges.

Any tips?

Note: Found this proof for $\dfrac12|E|$ but not $\dfrac23|E|$.