A finite group with n elements is generated by g and h. Can we arrange two copies of the elements of the group in a sequence (total length 2n) so that each element is g or h times the previous element and the first element is g or h times the last?
Solution
Regard the n elements as the points of a directed graph. We have a line from A to B if B = gA or B = hA. Then every point A of the graph has an equal number of incoming lines (just 2, from g-1A and h-1A) and outgoing lines (again just 2, to gA and hA). Also, the graph is connected since g and h generate the group. Hence it has an Eulerian cycle, which solves the problem.
The existence of such a cycle is a standard graph theory result. Any graph (connected or not) in which every point has equal number of incoming and outgoing lines (and there is at least one line) has a cycle. Start with a point P1 with at least one outgoing line. Take a line to P2. If P2 = P1 then we are done. If not, then P2 must have an outgoing line. And so on. Having got to Pm, if Pm belongs to {P1, ... , Pm-1} then we have a cycle (if Pm = Pj, then the cycle is PjPj+1 ... Pm). If not, then it must have an outgoing line. But the process must terminate since the graph has only finitely many points.
Now remove the lines in the cycle. The remaining graph has an equal number of incoming and outgoing lines at every point. So we can find another cycle. Continuing, we partition the lines of the original graph into disjoint cycles. We now build up the Eulerian cycle. Start from one of the cycles. If that exhausts the lines we are done. If not, there must be another cycle with a point P in common with it (otherwise the graph would be disconnected). Form a new cycle by traversing these two cycles successively. If this exhausts the lines, we are done. If not, we may extend it as before. The process terminates, since the graph has only finitely many lines.
© John Scholes
jscholes@kalva.demon.co.uk
1 Jan 2001