# A Universal Coloring

Sixtteen dots are arranged in a circular pattern. Each can be painted with one of four colors. Paint the dots in such a way that going around the circle in either direction you will meet all possible (ordered) pairs of two colors by inspecting successive dots [Bicycle, #129].

The applet below offers you a chance to solve similar problems with the number of colors ^{2}. (Dots cycle through available colors when clicked upon.)

What if applet does not run? |

### References

- J. Konhauser, D. Velleman, S. Wagon,
*Which Way Did the Bicycle Go?*, MAA, 1996, #129

|Activities| |Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

Sixtteen dots are arranged in a circular pattern. Each can be painted with one of four colors. Paint the dots in such a way that going around the circle in either direction you will meet all possible (ordered) pairs of two colors by inspecting successive dots.

What if applet does not run? |

One way to solve the problem is by relating a coloring of n^{2} dots with n colors to a *directed graph*. A *directed graph*, or *digraph*, is a combination of vertices and directed links or *arcs*. An arc on a digraph joins one vertex to another according to its direction which is usually indicated by an arrow. Thus it has a *starting* and an *ending* vertices. The two vertices may or may not be joined by an arc in the opposite direction. A vertex may be joined to itself, in which case the arc is known as a *loop*. On a digraph, each vertex has an *indegree* and an *outdegree*. The indegree equals the number of arcs that end at this vertex. In other words, the indegree of a vertex is the number of vertices joined to the given vertex. The outdegree is the number of arcs that join this vertex with other vertices. A path is a sequence of arcs in which the ending vertex of one arcs is simultaneously the starting vertex of the subsequent arc.

Let's now return to the problem of dots coloring. By fixing an orientation on the circle we make each pair of successive dots ordered. Consider a graph with n (= number of colors) vertices and paint each vertex with one of the given colors. We join two vertices with an arc iff there is an ordered pair of successive dots painted with exactly same colors. Obviously, solving the problem means finding a coloring of the dots which leads to a complete graph with n vertices, i.e. to the graph in which every vertex is joined to every other (itself, in particular) vertex.

We may also start with such a complete graph. Then a coloring of dots will correspond to a (closed) path on the graph. Within this interpretation we look for a coloring which generates an *Euler cycle* (also, an *Eulerian circuit*), i.e. a path that includes all the available arcs in some order and starts and ends at the same vertex. An Euler cycle exists on any digraph whose vertices have the property that, for each, the indegree equals the outdegree. This condition is obviously satisfied by a complete graph. Furthermore, we may start forming an Euler cycle at any vertex and proceed almost randomly: on a complete digraph there is no way to get stuck without completing the jobs!

Note that the dots coloring problem serves a particular case of de Bruijn's cycle construction.

### References

- N. Hartsfield, G. Ringel,
*Pearls in Graph Theory*, Dover, 1994 - V. K. Balakrishnan,
*Graph Theory*, Shaum's Outline Series, 1997

### de Bruijn Cycles

- de Bruijn Cycle: an Interactive Gizmo
- Existence of the de Bruijn Cycles via Graphs
- Constructive Existence of the de Bruijn Cycles
- Universal Coloring (an Interactive gizmo)
- From Lewis Carroll to Archimedes

|Activities| |Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

70553018