# Choosing two-colorable subgraph in a triangulation

Consider a planar graph $G$ which is a triangulation.

Is it possible to find a two-colorable subgraph $H$ of $G$ which has a common edge with every face of $G$?

It is known that it is not always possible to take $H$ to be a spanning tree. See this MO question.

Note that we do not require $H$ to be connected.

If it is true, is there an efficient algorithm to find such a subgraph?

• Just by curiosity: may you give an example of a triangulation without such a spanning tree? – Wolfgang Apr 29 '16 at 10:23

Yes, such a subgraph always exist. Let $G$ be a planar triangulation. By the $4$-colour theorem, $G$ has a $4$-colouring. We let $H$ be the subgraph consisting of all edges with endpoints coloured $1$ and $2$, or with endpoints coloured $3$ and $4$. Since every face of $G$ is a triangle, every face must contain a $12$ edge or a $34$ edge, as required. Also, $H$ is clearly bipartite since $(X,Y)$ is a bipartition of $H$ where $X$ is the set of vertices coloured $1$ or $3$ and $Y$ is the set of vertices coloured $2$ or $4$.
Regarding the algorithmic question, there is a quadratic algorithm to find such a subgraph. This follows from this paper of Robertson, Sanders, Seymour, and Thomas, where they present a quadratic algorithm to $4$-colour planar graphs.