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