# Planar graphs & Spanning trees

Does there exist a planar graph whose edges can be coloured either red, green or blue in such a way that the red edges form a spanning tree, the green edges form a spanning tree, and the blue edges form a spanning tree?

I know that a spanning tree must touch all nodes and this does not apply for a graph with 3 vertices, but I'm not quite sure how to go about proving that there does not exist.

-
To even have red, blue, and green spanning trees, every node must have at least degree 3, but you can't have more than $3|V|-6$ edges. –  Fixee Dec 9 '12 at 18:47

Every triangulation decomposes into 3 edge-disjoint spanning trees, when the edges of one triangular face are doubled. See here.

However, if you do not double the edges such a coloring is impossible, since a planar graph has at most $3n-6$ edges (Euler's formula) and three disjoint spanning trees, need $3(n-1)$ edges.

-
Isn't your second paragraph in itself enough? –  Hendrik Jan Dec 9 '12 at 20:09
Yes, but isn't it nice if you can tell something more. In this case you can see that the statement becomes true with a small modification. –  A.Schulz Dec 10 '12 at 19:10

The answer is no, except for the graph with only one vertex.

Let $G$ be a connected planar graph with $v$ vertices and $e_1,e_2$ and $e_3$ red, green and blue edges respectively. Assuming the red, green and blue edges form a spannig tree, we have $v - e_1 = v - e_2 = v - e_3 = 1,$ thus $e = 3v - 3$ where $e = e_1 + e_2 + e_3$ is the number of all edges of $G$. For $v \geq 3$ this contradicts $e \leq 3v - 6$, which must be satisfied by every connected planar graph with at least three vertices. The remaining cases are easily checked.

-