<p>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:</p>

<ul>
<li><p>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.</p></li>
<li><p>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.</p></li>
<li><p>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.</p></li>
<li><p>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.</p></li>
</ul>

<p>Incidentally, if $T$ has no degree two vertices, then $G(T)$ is called a <a href="http://en.wikipedia.org/wiki/Halin_graph">Halin graph</a>; 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.</p>

CC BY-SA 3.0
2013-04-21T16:15:08.243Z
That's the point. I want to prove that $G(T)$ is 3-colorable if $T\neq K_{1,2r+1}$.
user15735
CC BY-SA 3.0
2013-04-21T22:26:11.380Z
Ok, I expanded my answer to include a proof of that.
David Eppstein
CC BY-SA 3.0
2013-04-21T15:50:39.890Z
2013-04-21T22:25:57.787Z
2013-04-21T22:25:57.787Z
David Eppstein
<p>The proof I posted here (and at MathOverflow) yesterday is flawed.  Here is a corrected version:</p>

<p>As nvcleemp noted (at MathOveflow), one should start with a 2-coloring (Black and White) of the tree and, if the number of leaves is even, simply change every other leaf around the cycle to a third color (Red).  It's only if there is an odd number leaves that we have to do something fancier.  To handle that case, it's helpful to introduce a tiny bit of terminology:  Let's call the vertices that leaves are connected to "buds." </p>

<p>We'll start with a little lemma:</p>

<blockquote>
  <p>If the tree is not a star, then there
  are at least two buds for which the
  cycle traversing the leaves passes 
  <em>consecutively</em> through those buds' leaves.</p>
</blockquote>

<p>Proof:  </p>

<blockquote>
  <p>It's easy to see that this is true if
  there are only two buds.  The rest is
  by induction, which is easiest to
  picture if you imagine the graph
  deformed so that the cycle through the
  leaves is a circle.  Suppose there's a
  bud for which the cycle does not pass
  consecutively through its leaves. 
  Picture that bud as being at the center of the
  circle and two of its non-consecutive
  leaves at 12:00 and 6:00 on the
  circle, connected to the bud by radii.
  The non-consecutiveness means there
  are other buds connecting to other
  leaves on <em>each</em> side of the diameter
  just drawn.  This means there is a
  <em>smaller</em> tree on each side (including the bud and two leaves of the
  diameter), so induction applies.  One
  of the two consecutive-leaf buds for each
  side may be the bud at the center of
  the circle, but that still leaves at
  least one bud on each side for which
  the cycle passes through its leaves
  consecutively.</p>
</blockquote>

<p>We're now in position to complete the proof of 3-coloring for non-stars in the case of oddly many leaves.</p>

<p>Pick one of the buds for which the cycle passes consecutively through its leaves.  (The lemma guarantees us two, but we only need one.)  Change its color to Red.  Skipping its leaves for the moment, and starting with the "next" leaf (say running clockwise), turn every other leaf Red until you get back around to the Red bud's leaves, at which point you just need to alternate Black and White.  (Note, this works even for the "easy" case where the number of leaves is even.)</p>

CC BY-SA 3.0
2013-04-22T23:37:06.410Z
2013-04-22T23:37:06.410Z
Barry Cipra
<p><strong>Added 4/24/13</strong>:  I tried replacing this incorrect proof with a correct one yesterday, but for some reason was unable to do so, so I posted the correction separately.  There is no reason to read any further here, except perhaps for the link to mathoverflow. <strong>[end of addition]</strong></p>

<p>I posted the following proof at <a href="https://mathoverflow.net/questions/128169/3-coloring-of-specific-planar-graphs">https://mathoverflow.net/questions/128169/3-coloring-of-specific-planar-graphs</a> where the problem was cross posted (as fidbc noted in comments here and there):</p>

<p>Let's call the vertices that leaves are connected to "buds."  Note that the cycle traversing the leaves must pass <em>consecutively</em> through the leaves of each bud.  This makes everything easy.</p>

<p>As in nvcleemp's answer, start with a 2-coloring (Black and White) of the tree.  If the number of leaves is even, there's no problem changing every other one to a third color (Red).  If the number of leaves is odd and the tree is not a star, there are two possibilities:  either one of the buds has an even number of leaves, or all the buds have an odd number of leaves and there are an odd number of them (and that number is at least 3).</p>

<p>The case where there's a bud with an even number of leaves is easy to handle:  Take the portion of the cycle that doesn't contain that bud's leaves, note that it is a path connecting an odd number of leaves (since odd minus even is odd), and change every other leaf's color to Red, starting with the first and hence stopping with the last.  Finally, change the selected bud's color to Red and alternate its leaves Black and White.</p>

<p>The case where there are an odd number of buds, each with an odd number of leaves, is a little trickier.  For the moment, retract all the leaves down to their buds, dragging the cycle with them.  Some of the edges of this "retraction" cycle might coincide with edges connecting buds of the underlying tree, but they can't all coincide -- there must be at least two "consecutive" buds on the retraction cycle that are not in fact connected.  (This is where non-starness is assumed.)  Now color these two buds Red. Finally, undo the retraction of the original cycle's leaves and, starting with the first first leaf of the first non-Red bud, color every other leaf Red.  Since there's an odd number of buds each with an odd number of leaves, this changes the last leaf of the last non-Red bud to Red, leaving only the leaves of the two Red buds, which can be colored alternately Black and White.</p>

CC BY-SA 3.0
2013-04-21T22:55:33.913Z
2013-04-24T19:40:19.583Z
2017-04-13T12:57:54.530Z
Barry Cipra
<p>May be one should be more specific about the construction of G(T) from T. Consider the following (counter)-example: E(T) = {(1,2), (1,3), (1,4)} and then you form G(T) by adding the edge-set: {(2,3), (3,4), (4,2)} then there is surely a planar-embedding of the graph but is not 3-colorable! I know I've been too generous (:) ) in the construction of G(T).</p>

CC BY-SA 3.0
2013-04-21T15:40:37.707Z
your tree is the $K_{1, 2r+1}$!
user13136
CC BY-SA 3.0
2013-04-22T07:37:13.383Z
yup my bad - thx for pointing out
Ram
CC BY-SA 3.0
2013-04-21T15:34:07.280Z
2013-04-21T15:34:07.280Z
Ram
<blockquote>
  <p>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.</p>
</blockquote>

<p>In case I wasn't clear enough I'll give an example:</p>

<p>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. </p>

<p>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. </p>

CC BY-SA 3.0
2013-04-21T13:29:39.010Z
It would seem easier to colour the cycle first, trying to use colours so that the parents of leaves at the same level are assigned only two colours.
András Salamon
CC BY-SA 3.0
2013-04-21T21:10:34.110Z
This question appears to be crossposted in MathOverflow. http://mathoverflow.net/questions/128169/3-coloring-of-specific-planar-graphs
fidbc
<planar-graphs>
3-coloring of specific planar graphs
user15735
# 3-coloring of specific planar graphs

(Asked by: username_0 on 2013-04-21)

> 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.

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.

**Tags:** planar-graphs
> **Comments:**
> **username_1**: It would seem easier to colour the cycle first, trying to use colours so that the parents of leaves at the same level are assigned only two colours.  
> **username_2**: This question appears to be crossposted in MathOverflow. http://mathoverflow.net/questions/128169/3-coloring-of-specific-planar-graphs  

---

## 4 answers

### Answer by username_3 on 2013-04-21. Score: 6

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](http://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_0**: That's the point. I want to prove that $G(T)$ is 3-colorable if $T\neq K_{1,2r+1}$.  
> **username_3**: Ok, I expanded my answer to include a proof of that.  

---

### Answer by username_4 on 2013-04-22. Score: 1

The proof I posted here (and at MathOverflow) yesterday is flawed. Here is a corrected version:

As nvcleemp noted (at MathOveflow), one should start with a 2-coloring (Black and White) of the tree and, if the number of leaves is even, simply change every other leaf around the cycle to a third color (Red). It's only if there is an odd number leaves that we have to do something fancier. To handle that case, it's helpful to introduce a tiny bit of terminology: Let's call the vertices that leaves are connected to "buds."

We'll start with a little lemma:

> If the tree is not a star, then there
> are at least two buds for which the
> cycle traversing the leaves passes
> *consecutively* through those buds' leaves.

Proof:

> It's easy to see that this is true if
> there are only two buds. The rest is
> by induction, which is easiest to
> picture if you imagine the graph
> deformed so that the cycle through the
> leaves is a circle. Suppose there's a
> bud for which the cycle does not pass
> consecutively through its leaves.
> Picture that bud as being at the center of the
> circle and two of its non-consecutive
> leaves at 12:00 and 6:00 on the
> circle, connected to the bud by radii.
> The non-consecutiveness means there
> are other buds connecting to other
> leaves on *each* side of the diameter
> just drawn. This means there is a
> *smaller* tree on each side (including the bud and two leaves of the
> diameter), so induction applies. One
> of the two consecutive-leaf buds for each
> side may be the bud at the center of
> the circle, but that still leaves at
> least one bud on each side for which
> the cycle passes through its leaves
> consecutively.

We're now in position to complete the proof of 3-coloring for non-stars in the case of oddly many leaves.

Pick one of the buds for which the cycle passes consecutively through its leaves. (The lemma guarantees us two, but we only need one.) Change its color to Red. Skipping its leaves for the moment, and starting with the "next" leaf (say running clockwise), turn every other leaf Red until you get back around to the Red bud's leaves, at which point you just need to alternate Black and White. (Note, this works even for the "easy" case where the number of leaves is even.)


---

### Answer by username_4 on 2013-04-21. Score: 0

**Added 4/24/13**: I tried replacing this incorrect proof with a correct one yesterday, but for some reason was unable to do so, so I posted the correction separately. There is no reason to read any further here, except perhaps for the link to mathoverflow. **[end of addition]**

I posted the following proof at <https://mathoverflow.net/questions/128169/3-coloring-of-specific-planar-graphs> where the problem was cross posted (as fidbc noted in comments here and there):

Let's call the vertices that leaves are connected to "buds." Note that the cycle traversing the leaves must pass *consecutively* through the leaves of each bud. This makes everything easy.

As in nvcleemp's answer, start with a 2-coloring (Black and White) of the tree. If the number of leaves is even, there's no problem changing every other one to a third color (Red). If the number of leaves is odd and the tree is not a star, there are two possibilities: either one of the buds has an even number of leaves, or all the buds have an odd number of leaves and there are an odd number of them (and that number is at least 3).

The case where there's a bud with an even number of leaves is easy to handle: Take the portion of the cycle that doesn't contain that bud's leaves, note that it is a path connecting an odd number of leaves (since odd minus even is odd), and change every other leaf's color to Red, starting with the first and hence stopping with the last. Finally, change the selected bud's color to Red and alternate its leaves Black and White.

The case where there are an odd number of buds, each with an odd number of leaves, is a little trickier. For the moment, retract all the leaves down to their buds, dragging the cycle with them. Some of the edges of this "retraction" cycle might coincide with edges connecting buds of the underlying tree, but they can't all coincide -- there must be at least two "consecutive" buds on the retraction cycle that are not in fact connected. (This is where non-starness is assumed.) Now color these two buds Red. Finally, undo the retraction of the original cycle's leaves and, starting with the first first leaf of the first non-Red bud, color every other leaf Red. Since there's an odd number of buds each with an odd number of leaves, this changes the last leaf of the last non-Red bud to Red, leaving only the leaves of the two Red buds, which can be colored alternately Black and White.


---

### Answer by username_5 on 2013-04-21. Score: 0

May be one should be more specific about the construction of G(T) from T. Consider the following (counter)-example: E(T) = {(1,2), (1,3), (1,4)} and then you form G(T) by adding the edge-set: {(2,3), (3,4), (4,2)} then there is surely a planar-embedding of the graph but is not 3-colorable! I know I've been too generous (:) ) in the construction of G(T).

> **Comments:**
> **username_6**: your tree is the $K_{1, 2r+1}$!  
> **username_5**: yup my bad - thx for pointing out  

---

