Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

2 Answers

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.

share|improve this answer
    
Isn't your second paragraph in itself enough? –  Hendrik Jan Dec 9 '12 at 20:09
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. –  A.Schulz Dec 10 '12 at 19:10
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.