Tree Coloring

Flash and JavaScript are required for this feature.

Download the video from iTunes U or the Internet Archive.

PROFESSOR: Now we can use the unique path characterization of trees to very quickly figure out that every tree is 2-colorable. So we know that a tree is a graph with unique paths between every pair of vertices. And as a consequence, the chromatic number of a tree with two or more vertices is 2.

The proof is just to show you how to color it. You clearly can't get by with one color if you've got any two adjacent vertices. The 2-colorable way is that you just choose an arbitrary vertex and-- call it the root-- but you make the arbitrary choice on what the root is.

And there's a unique path from the root to every vertex, using this unique path characterization. And so we're just going to color vertices by whether the path from the root is of odd or even length.

If it's of even length, color it red. And if it's odd length, color it green. And so we wind up alternating red and green. And the fact is that adjacent nodes are going to be at a distance where one is an odd distance and one is an even distance, which is why this method of coloring is going to work.

A general property of 2-coloring is that to figure out whether or not a graph is 2-colorable and how to do it, is you just start. Pick an arbitrary vertex, color it red. And then color all the vertices adjacent to it green. And keep going in that way, coloring a vertex with a color different from an adjacent vertex that's colored, until you get stuck.

If you don't get stuck it's 2-colorable. And if it's not 2-colorable, you're guaranteed to get stuck.

So it's a very easy way to figure out if a graph is 2-colorable. Another characterization of 2-colorability in general, is that a graph is 2-colorable providing that all the cycles that it has, if any, are of even lengths. Of course, a tree has no cycles, so that makes it 2-colorable for sure.

Free Downloads

Video


Caption

  • English-US (SRT)