Properties of Tait-colored graphs

[Much of this post and the previous one is drawn from Marijke van Gans' 2007 doctoral thesis, "Topics in Trivalent Graphs."]

A proper edge coloring of a graph is a coloring of its edges such that nowhere are two edges of the same color incident to a node. A proper edge coloring of a cubic graph using three colors is called a Tait coloring. (Note, that if a cubic graph has a Tait coloring, it may well have many.)

An example of a trivalent graph that does not have a Tait coloring is the Peterson graph.

Nearly all cubic graphs have a Tait coloring. The Petersen graph is an example of one that does not.

Because each edge in a Tait-colored graph belongs to two cycles of alternating edge colors, no graph with a bridge can have a Tait coloring. (More obviously, no graph with a self-loop can have a Tait coloring, but all such cubic graphs have a bridge as well.)

Every bicubic (bipartite cubic) graph has a Tait coloring.

Every Hamiltonian cubic graph has a Tait coloring.

Since nearly all cubic graphs are Hamiltonian, it follows that nearly all are Tait-colorable.

Every bridge-free, planar cubic graph has a Tait coloring. (A consequence of the Four Color Theorem.)

A Heawood node 2-coloring is a node-2-coloring of a plane (i.e., embedded planar) graph under the condition that the number of black and white nodes in every face cycle are equal mod 3. A bridge-free planar, cubic graph can be Tait colored if and only if it can be Heawood node-2-colored; hence, as a consequence of the Four Color Theorem, every bridge-free, planar cubic graph can be Heawood node 2-colored.