Coloring Trees by Alternating Levels

Rooting a Tree and Assigning Levels

A tree can be colored without making a sequence of local choices: choose any vertex as a root, measure every vertex’s distance from it, and alternate two colors as the distance increases. The key fact that makes this work is specific to trees: every edge joins vertices whose distances from the root differ by exactly one. We will prove that fact and then use it to establish the chromatic number of every tree, including the one-vertex case.

All graphs in this tutorial are finite and simple. A path is a sequence of distinct vertices in which consecutive vertices are adjacent. Its length is the number of edges in the sequence. A cycle is a sequence \(v_0,v_1,\ldots,v_k\) with \(k\ge 3\), \(v_0=v_k\), \(v_0,\ldots,v_{k-1}\) distinct, and consecutive vertices adjacent. A graph is connected if there is a path between every pair of distinct vertices.

A tree is connected, so each vertex has a path from the root. We first establish that this path is unique; this ensures that the levels describe a single, well-defined route outward from the root.

Proof. Let \(u\) and \(v\) be distinct vertices of a tree. Connectedness gives at least one \(u\)-\(v\) path. Suppose there are two different such paths. Starting from \(u\), take their first point of divergence and then follow the paths until the first point where the diverging portions meet again; such a meeting exists at least at \(v\). The two portions between these points have no common internal vertex, by the choice of the first meeting. Following one portion forward and the other backward therefore gives a cycle. Its length is at least \(3\): the portions are distinct, and in a simple graph they cannot both be the same single edge. This contradicts that a tree has no cycles. Thus the path is unique. \(\square\)

Every Edge Joins Consecutive Levels

Proof. Let \(P_u\) and \(P_v\) be the unique paths from \(r\) to \(u\) and from \(r\) to \(v\). First consider the case where neither endpoint lies on the root path to the other: \(u\) is not on \(P_v\), and \(v\) is not on \(P_u\). The paths share an initial segment from \(r\), and after they diverge they cannot meet again, since that would give two different paths between a pair of vertices, contrary to the preceding lemma. Their two tails, together with the edge \(uv\), form a cycle. This is impossible in a tree. Therefore one endpoint lies on the root path to the other; suppose, for example, that \(u\) lies on \(P_v\).

The part of \(P_v\) from \(u\) to \(v\) is a path between \(u\) and \(v\). The edge \(uv\) is also a path between them. By uniqueness of paths, these must be the same path, so the part of \(P_v\) from \(u\) to \(v\) consists of the single edge \(uv\). Consequently \(d(r,v)=d(r,u)+1\). If instead \(v\) lies on \(P_u\), the same argument gives \(d(r,u)=d(r,v)+1\). In either case the levels differ by exactly one. \(\square\)

In particular, an edge never joins vertices at the same level, and it does not skip a level. This conclusion depends on the graph being a tree: for a general graph, adjacent vertices can lie at the same distance from a chosen root.

Alternating Colors by Level

For a rooted tree, assign one color to vertices on even levels and a second color to vertices on odd levels. The edge-level lemma proves this is proper: along every edge the level changes by exactly one, so its endpoints have opposite parity and therefore different colors.

Proof. Let \(T\) have at least two vertices, choose any root \(r\), and assign color \(A\) to vertices at even distance from \(r\) and color \(B\) to vertices at odd distance from \(r\). The edge-level lemma shows that the endpoints of every edge lie on consecutive levels. Consecutive integers have opposite parity, so every edge has one endpoint colored \(A\) and the other colored \(B\). This is a proper coloring, and hence \(\chi(T)\le 2\).

Because \(T\) is connected and has at least two vertices, there is a path between two distinct vertices. That path contains an edge. The endpoints of an edge must have different colors in any proper coloring, so one color cannot suffice; thus \(\chi(T)\ge 2\). Combining the two bounds gives \(\chi(T)=2\).

Now suppose \(T\) has exactly one vertex. Assigning one color to that vertex is proper, since there are no edges whose endpoints need different colors. A coloring uses a color on each vertex, so a nonempty graph cannot be colored with zero colors. Therefore \(\chi(T)=1\). \(\square\)

The root is arbitrary. Choosing a different root may change which vertices receive color \(A\) and which receive color \(B\), but the same edge-level proof applies. The result concerns the existence of a proper coloring with two colors, not a unique assignment of color names.

Why the Tree Condition Matters

The level argument is useful because it gives both a coloring and a direct verification: calculate distances from a root, divide vertices by parity, and use the edge-level lemma to check every edge at once. In applications, this can express a two-way division of the vertices in which adjacent vertices belong to opposite groups. It also gives an optimal coloring immediately for any tree with an edge; there is no need to search through possible color assignments.

A common mistake is to assume that every edge of every graph joins different levels. For a concrete counterexample, take the triangle \(G\) with \(V(G)=\{1,2,3\}\), \(E(G)=\{12,13,23\}\), and root \(1\). The distances are \(d(1,1)=0\), \(d(1,2)=1\), and \(d(1,3)=1\). The edge \(23\) joins two vertices at the same level. Coloring by level parity would give both \(2\) and \(3\) the same color, so that coloring would not be proper.

The correction is to check the hypothesis before using the level argument. The triangle is not a tree: it is connected, but it has the cycle \(1,2,3,1\). In a tree, the unique-path property rules out an edge joining two vertices at the same level. The theorem does not say that alternating levels properly colors every rooted graph; it says that it works for rooted trees because their edges must join consecutive levels.

There is a separate small-case pitfall: saying “a tree uses exactly two colors” without excluding the single-vertex tree. The two-color assignment is still a proper coloring of a single vertex, but it is not minimal. The chromatic number is \(1\) there. For every tree with at least two vertices, connectedness guarantees at least one edge, which forces the chromatic number to be \(2\).