A Tait coloring of a trivalent (aka cubic) graph is a coloring of its edges with only three colors, such that at each vertex the colors of the three edges there are different. After Peter G. Tait (1831-1901), Scottish physicist, who in 1880 proved the following

Theorem (Tait) A bridge-free trivalent plane graph can be face-colored with 4 colors if and only if it can be edge-colored with 3 colors.

This introduction to face- and edge-colorings of plane graphs has a proof of the theorem.

To put this in a modern context, Vizing's theorem says that graphs fall into two classes: those that can be colored with colors and those that need colors, where is the largest valency that occurs in . When applied to trivalent graphs that means 3 and 4 colors, respectively. It is known that “almost all” are in the first class -- this expression has a technical meaning (for increasing graph size, the proportion of them in the second class tends to zero).

Thanks to Tait's result, it is a corollary of the four-color theorem that all planar trivalent graphs are in the first class (can be edge-3-colored). The converse is not the case. Many trivalent graphs, in fact almost all of them, can be edge-3-colored and yet are not planar. is one example.

The Petersen graph is an example of a trivalent graph that needs 4 colors.