Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

So this question is seriously flooring me.

Let $G$ be drawn in the plane so that it satisfies:

  1. The boundary of the infinite region is a cycle $C$
  2. Every other region has boundary cycle of length $3$
  3. Every vertex of $G$ not in $C$ has even degree

Show that $\chi(G) \le 3$, where $\chi(G)$ is the chromatic number.

I know I have to use induction and consider two cases for the first step: Whether some two non-consecutive vertices of $C$ are adjacent and in the second case I would delete an edge of $C$ and apply the induction hypothesis.

Can anyone help?

share|cite|improve this question

This came up on CS Theory a while back:

Unfortunately some of the links in that post are dead / not free.

This paper proves a special case of what you mention, that if all vertices are of even degree in a near-triangulation, then the graph is 3-colorable. The key is that such a graph is eulerian, and therefore has an eulerian trail that doesn't cross over itself. Coloring vertices 1, 2, 3, 1, 2, 3, etc. along this trail is a proper 3-coloring.

For the case when $G$ has odd vertices on its boundary, you can construct a planar Eulerian near-triangulation $H$ such that $G \subset H$ and $H$ is Eulerian. Let $C = v_1v_2\ldots v_x$ and suppose $v_j$ and $v_k$ on $C$ are of odd degree. WLOG $k > j$. Add vertices $u_ju_{j+1}\ldots u_{k-1}$ in the exterior region in the obvious order. Then add the edges $v_iu_i$ and $v_{i+1}u_i$ for $j \le i \le k-1$. Now $u_j$ and $u_{k-1}$ are both of odd degree unless $j = k-1$, but we can repeat this process until these two odd vertices are resolved (since the odd vertices continue to get closer). We now have fewer odd vertices, so repeating this process can make all vertices even.

share|cite|improve this answer
This book contains a paper that might be of interest. The proof that they provide for this result (lemma $1$, page $141$) is quite clever, but the construction they give on the figure seems off (I failed to complete the triangulation as they indicated). Perhaps you can make something of it. – EuYu Nov 24 '12 at 6:45
The proof of Lemma 1 does the same work as my last paragraph. The reduction there is more efficient, but more confusing. They're showing that you can turn the graph "inside-out" by making the exterior region an interior one. Then, if you put the original graph into that interior region and merge corresponding vertices along C, you still have a triangulation and the vertices on the cycle have their degree doubled, so everything is even. This is also a nice proof that you can add edges to a near-triangulation to get a triangulation (though there are simpler proofs). – William Macrae Nov 24 '12 at 7:10
thanks for the help! though I'm pretty sure there's a significantly easier way to do this with induction using two different cases as I mentioned above. given that every other region has even degree and are all cycles of length 3, they're at most three colourings. for the outer cycle C, some vertices could have edges connecting each other thereby possibly increasing the chromatic number, hence why we would separate the cases. – user50573 Nov 24 '12 at 23:14
Please do not comment on an answer. Comments are for that. Also, I'm not sure why you are using a different user. It might be better if you stick to one of them. – Martin Argerami Nov 24 '12 at 23:56
Let us know if you find a correct proof by induction. I think this might be harder to prove than it seems though, and so an inductive proof would have to be very diligently crafted. – William Macrae Nov 25 '12 at 6:13

We induct on $|E(G)|$. The base case is trivial.

Suppose first that there are two non-consecutive vertices $u, v$ of $C$ which are adjacent. Let $e$ be the edge joining them. Then, $e$ partitions the graph into two graphs $G_1$ and $G_2$ on either side of $e$ in the plane, both of which satisfy the induction hypothesis, so $\chi(G_1), \chi(G_2) \leq 3$. Permuting the colors of (say) $G_2$ appropriately so that $u$ and $v$ are colored identically in $G_1$ and $G_2$, we obtain a 3-coloring of $G$, so $\chi(G) \leq 3$.

Otherwise, no two nonconsecutive vertices of $C$ are adjacent. Let $w_0, w_1$ be any consecutive vertices on $C$. We know that there is a vertex $u \in V(G) - V(C)$ with $w_0 u, w_1 u \in E(G)$. By the induction hypothesis, the graph $G' = G \setminus w_0 w_1$ has $\chi(G') \leq 3$. I claim that any 3-coloring of $G'$ has $w_0$ and $w_1$ as different colors, so that this coloring extends to a 3-coloring of $G$.

Suppose not, i.e. $w_0$ and $w_1$ are colored identically, and $u$ is colored differently. Consider the triangles incident to $u$, with vertices $u w_i w_{i + 1}$. Since $u$ has even degree, then the path $P = w_1 w_2 \ldots w_{\deg(u) - 1} w_0$ has odd length. Our 3-coloring of $G'$ determines that $P$ is 2-colored, and a 2-colored odd path has opposite colored ends (easily verified), which is a contradiction.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.