Take a root with children . Give the children , give the children , and give the children . The root of a tree has degree two, the three vertices have degree three, and are the five leaves of a graph. There are nine vertices and eight edges, as required by the handshaking lemma and the edge count for a tree.
A plane tree has one face of a plane graph, so its dual graph has one vertex. Every original edge is a bridge incident to that same face on both sides, so every dual edge is a loop. Thus the dual drawing in the figure is a bouquet of eight loops, arranged with the displayed nesting inherited from the tree. It has nine faces of a plane graph, matching . The nesting matters for which faces meet; a bouquet drawn as eight unrelated petals would have a different face-adjacency graph.
Two dual faces of a plane graph share an edge exactly when their corresponding original vertices are adjacent. Their face-adjacency graph is therefore the original tree, which is a nontrivial bipartite graph. Colour the face for with one colour and alternate along the original tree. This gives a proper face colouring with two colours, and at least two are needed because there is an edge separating distinct faces. Hence the minimum is
Articles by others on the same topic
There are currently no matching articles.