I've got a specific type of the planar graph and I found it interesting to search for an algorithm which will color its vertices legally. About this type of graph, it's very easy and cool:

Consider any tree $T$ with $n>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.

And the problem I came up with is to color $G(T)$ with $3$ colors. Clearly, $G(T)$ as a planar graph, is $4$-colorable, but I think (don't have a proof) that it is almost always $3$-colorable due to its simplicity. Almost always means that only if $T$ is a star and only with odd number of leaves, then $G(T)$ is not $3$-colorable.

I am looking for some algorithm $3$-coloring this graph, or maybe proof of my assumptions that this class of planar graphs is $3$-colorable which could be transformed into an algorithm. I would be very very grateful for any help, hints.

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.