3-coloring of specific planar graphs Consider any tree $T$ with $n&gt;2$ vertices and $k$ leaves. Let's denote $G(T)$ a graph constructed from $T$ by connecting its leaves into $k$-cycle in such way that $G(T)$ is planar.


In case I wasn't clear enough I'll give an example:

Let T be a tree with edges E(T) = { {1,2}, {2,3}, {2,4}, {4,5} } and then E(G(T)) = sum of the sets: E(T) and { {1,5}, {5,3}, {3,1} }, since we are connecting leaves 1,5,3 into a cycle. 

And I believe that if $T$ is not $K_{1,2r+1}$ then $G(T)$ is $3$-colorable, but my problem is I don't know how to prove it. I was trying to come up with an algorithm that starts with $2$-coloring of a tree and then with third color fix collisions on a cycle, but this led me to nowhere.
To prove that every tree with two or more internal nodes gives you a 3-colorable graph, use induction on the number of nodes of the tree. If you orient the tree from an arbitrarily chosen root node, there always exists an internal node $v$ whose children are all leaves. Now split into cases:


If $v$ has one child, then the graph can be reduced down to nothing by repeatedly removing vertices of degree at most two, and three-colored by reinserting the vertices in the reverse order and giving them a color distinct from their two neighbors.
If $v$ has three or more children, then the tree can be reduced in size by removing two consecutive children, forming the graph by connecting the remaining leaves into a cycle, and then coloring the smaller graph. The remaining children of $v$ must alternate in color and reinserting the removed children maintains the same alternation.
If $v$ has exactly two children, and there are three or more internal nodes, then remove $v$ and its two children from $T$, form  the graph by connecting the remaining leaves into a cycle, and then color it. Let $p$, $q$, and $r$ be the parent of $v$, the node to the left of $v$'s left child in the leaf cycle, and the node to the right of $v$'s right child in the leaf cycle; $q$ and $r$ are adjacent in the smaller graph, so must have different colors. There are two subcases. If $p$, $q$, and $r$ use only two colors among them, then the two children of $v$ can be colored in alternation with $q$ and $r$ using the same two colors, and $v$ can be given the remaining third color. On the other hand, if $p$, $q$, and $r$ use three different colors, then $v$ can be given $q$'s color, the left child of $v$ can be given $r$'s color, and the right child of $v$ can be given $p$'s color.
In the remaining base case, $T$ has exactly two internal nodes, each adjacent to two leaves. The graph is the graph of a triangular cylinder, which can be three-colored.


Incidentally, if $T$ has no degree two vertices, then $G(T)$ is called a Halin graph; with or without the degree two restriction, it has bounded treewidth, so an alternative method for finding an optimal coloring in linear time is to use dynamic programming. However, this method does not tell you ahead of time which trees require only three colors.