Planar graph contains bipartite subgraph

Question

I ran into the following question:

Let $G=(V,E)$ be a planar graph. Prove that the graph has a bipartite subgraph that contains at least $2/3$ of the edges from $G$.

I tried building an algorithm for deleting edges from faces with an odd length, but I was told that there too many cases and it won't work on all the cases.

Answer 1

I suppose you are permitted to use the four color theorem, that every planar graph is $4$-colorable. Thus it will suffice to prove the more general statement: Every $4$-colorable graph $G$ has a bipartite subgraph which contains at least $2/3$ of the edges of $G.$

Let $G=(V,E)$ be a $4$-colorable graph. Let $$V=V_1\cup V_2\cup V_3\cup V_4$$ be a partition of $V$ into four independent sets. Then $$E=E_{1,2}\cup E_{3,4}\cup E_{1,3}\cup E_{2,4}\cup E_{1,4}\cup E_{2,3}$$ where $E_{i,j}$ is the set of all edges of $G$ with one endpoint in $V_i$ and the other in $V_j.$ Since $$|E|=|E_{1,2}\cup E_{3,4}|+|E_{1,3}\cup E_{2,4}|+|E_{1,4}\cup E_{2,3}|,$$ it follows that $$\min\{|E_{1,2}\cup E_{3,4}|,\ |E_{1,3}\cup E_{2,4}|,\ |E_{1,4}\cup E_{2,3}|\}\le\frac13|E|.$$ Assume w.l.o.g. that $|E_{1,2}\cup E_{3,4}|\le\frac13|E|$ and let $$F=E\setminus(E_{1,2}\cup E_{3,4})=E_{1,3}\cup E_{2,4}\cup E_{1,4}\cup E_{2,3}.$$ Then $(V,F)$ is a bipartite subgraph of $G$ with bipartition $V'=V_1\cup V_2$ and $V''=V_3\cup V_4,$ and $|F|\ge\frac23|E|.$

More generally, if $\chi(G)\le 2n,$ then $G$ has a bipartite subgraph $H$ with $e(H)\ge\frac n{2n-1}e(G),$ where $e(\cdot)$ denotes the number of edges.

Answer 2

Here's a different proof sketch that does not use the four-colour theorem, which works for planar graphs with multi-edges but no self-loops (if there are self-loops, it is easy to construct examples where the statement is not true). Say $H$ is the dual graph of $G$ (assuming a planar embedding of $G$).

1. Note that a bipartition of the vertices of $G$, also known as a cut, corresponds to a unique even subgraph of $H$ of the same size. Essentially, the duals of the edges in the cut of $G$ form an even subgraph of $H$. Therefore, it suffices to show that $H$ has an even subgraph of size at least $2m/3$, where $m$ is the number of edges in $G$ or $H$.

2. Since $G$ has no self-loops, $H$ is $2$-edge connected (i.e., bridgeless). Note that $H$ could have self-loops.

The rest of the proof follows Bermond, Jackson, Jaeger, "Shortest Coverings of Graphs with Cycles" J. Combinatorial Theory, Ser. B 35 (1983), pp. 297-308. In particular, we don't need planarity of $H$ in the following, and hence we don't need the four-colour theorem.

3. Say $v$ is a vertex in $H$. A vertex-splitting of $H$ at $v$ is the graph $H'$ obtained by replacing $v$ with two vertices $v'$ and $v''$ such that any edge incident to $v$ is incident to either $v'$ or $v''$ (but not both) and degree of $v''$ is $2$. In particular, $H'$ also has $m$ edges, but more vertices with smaller degrees. By a sequence of such vertex-splittings, one can reach a graph $\tilde H$ that is still $2$-edge connected, has no self-loops, and all vertices have degree at most $3$. It suffices to show that $\tilde H$ has an even subgraph of size at least $2m/3$ because picking the corresponding edges in $H$ does the job.

4. If $\tilde H$ has no degree-$3$ vertices, then all vertices have degree $2$ and we are done. If not, let $T$ be the set of vertices of degree $3$ in $\tilde H$. Define the graph $K$ on the vertex-set $T$ such that there is an edge in $K$ between $u,v\in T$ for every path between $u$ and $v$ in $\tilde H \setminus T$ (there could be multiple edges if there are multiple paths). In other words, we recursively contract edges incident to degree-$2$ vertices until we are left with only degree-$3$ vertices. Note that $K$ is a $2$-edge connected, $3$-regular graph. Moreover, give each edge $e$ in $K$ a weight $f(e)$ equal to the length of the corresponding path in $\tilde H$. It suffices to show that $K$ has a perfect matching $M$ with weight at most $m/3$, i.e., $f(M) := \sum_{e\in M} f(e) \le m/3$ (note that the existence of a perfect matching in $K$ is ensured by Petersen's theorem). This is because the complement of $M$ in $K$ corresponds to an even subgraph of $K$ with weight at least $2m/3$, which corresponds to an even subgraph of $\tilde H$ with size at least $2m/3$.

5. Every matching $M$ in $K$ is associated with a characteristic vector in $\{0,1\}^{|E(K)|} \subset \mathbb R^{|E(K)|}$. The convex hull of all such characteristic vectors is known as the perfect matching polytope of $K$, denoted as $C(K)$. By the perfect matching polytope theorem of Edmonds, an equivalent characterisation of that polytope is given by the following: $C(K)$ is the set of all points $x\in \mathbb R^{|E(K)|}$ such that

   • $0\le x(e) \le 1$, for all $e\in E(K)$,

   • $x(\delta(\{v\})) = 1$, for all $v\in V(K) = T$,

   • $x(\delta(U)) \ge 1$, for all $U \subseteq V(K) = T$ such that $|U|$ is odd.

   Here, $\delta(U)$ denotes the set of edges in the cut associated with the bipartition $U$ and $T\setminus U$, and for any $J\subseteq E(K)$, define $x(J) := \sum_{e\in J} x(e)$. Any point $x$ that satisfies the above three properties is also known as a fractional perfect matching.

6. Since $K$ is $2$-edge connected and $3$-regular, it is easy to see that $x^* = (1/3,\ldots,1/3)$ is in $C(K)$. It follows from the perfect matching polytope theorem that there are perfect matchings $M_1,\ldots,M_r$ with characteristic vectors $x_1,\ldots,x_r$ and real constants $0\le \alpha_1,\ldots,\alpha_r\le1$ such that $\alpha_1 + \cdots +\alpha_r = 1$ and $\alpha_1 x_1 + \cdots + \alpha_r x_r = x^*$. Assume that $f(M_i) > m/3$ for all $i=1,\ldots,r$. Then, on one hand, we have $$\sum_{e\in E(K)} f(e) x^*(e) = \frac13 \sum_{e\in E(K)} f(e) = \frac{m}3.$$ On the other hand, we have $$\sum_{e\in E(K)} f(e) \sum_{i=1}^r \alpha_i x_i(e) = \sum_{i=1}^r \alpha_i \sum_{e\in E(K)} f(e) x_i(e) = \sum_{i=1}^r \alpha_i f(M_i) > \frac{m}3,$$ which is a contradiction. Hence, there is an $i$ such that $f(M_i) \le m/3$, which is what we wanted to show.