6
$\begingroup$

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.

  • 0
    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.2012-12-09

2 Answers 2

7

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.

  • 2
    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.2012-12-10
3

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.