What is the necessary and sufficient condition for existence of a three coloured alternating Eulerian tour to exist in a graph?

Question

NOTE : An Eulerian tour in G is called alternating if successive edges of the tour alternate in colour.

Here is what I came up with -

Firstly for an Eulerian tour to exist the graph must be connected and each vertex should have an even degree.

Now if we look at any arbitrary vertex in the graph, whenever we 'enter' it through an edge we need a different colour edge to 'exit' it.

Therefore, any single colour shouldn't dominate over other colour edges.

In other words, if degree of a vertex is k then an edge of a particular colour shouldn't be incident more than k/2 times.

I know this is a necessary condition but is it sufficient ?

And how can be extended for more than 3 colours.

Any help is appreciated. Thanks !

Answer 1

Your condition is sufficient.

Suppose that the graph is connected, and each vertex has an even degree, with no more than half the vertices being assigned any given color.

We can begin by finding something that "locally looks like" an Eulerian tour. At each vertex $v$, pair up the edges $vw_1, vw_2, \dots, vw_k$ out of $v$ so that no edge is ever paired with another edge of the same color. If your condition is satisfied, we can always do this with a greedy algorithm: just pair two edges in the two most common colors (leaving no color used on more than half of the unpaired edges) and repeat on the edges left over.

After we have a pairing of the edges at each vertex, we get a decomposition of the graph into alternating closed walks. Starting at an edge $v_1 v_2$, continue with the edge $v_2 v_3$ that it was paired to at $v_2$, then with the edge $v_3 v_4$ that was paired with $v_2 v_3$ at $v_3$, and so on; keep going until you end up at the edge $v_1 v_2$ again.

This is not yet an Eulerian tour, but only because there might be more than one closed walk in the decomposition. So our next step is to glue the closed walks, two at a time, reducing their number until only one is left over.

Pick two closed walks that pass through the same vertex. (Since the graph is connected, as long as there is more than one closed walk, some of them share vertices.) Let's say that one of the walks goes from $w_1$ to $v$ to $w_2$, and the other walk goes from $w_3$ to $v$ to $w_4$.

We can combine the two closed walks in two ways (that might not both alternate colors):

1. Go from $w_1$ to $v$ to $w_3$, follow the second walk until we take the edge from $w_4$ to $v$, and then go to $w_2$ and follow the first walk until we get back to the edge from $w_1$ to $v$.
2. Go from $w_1$ to $v$ to $w_4$, follow the second walk until we take the edge from $w_3$ to $v$, and then go to $w_2$ and follow the first walk until we get back to the edge from $w_1$ to $v$.

At least one of these is actually an alternating walk. If the edges $vw_1, vw_2, vw_3, vw_4$ include three different colors, we can just pick the option that doesn't try to pair the two edges of the same color. If the edges $vw_1, vw_2, vw_3, vw_4$ include two pairs of edges of the same color (say, red and blue), then each pair $(vw_1, vw_2)$ and $(vw_3, vw_4)$ includes a red edge and a blue edge, since we started with two alternating walks, we can pair the red edge from the first walk with the blue edge from the second walk, and vice versa.

Repeat this "gluing" procedure until only one closed walk is left, and you have an alternating Eulerian tour.

Finally, if you look at the proof, the same argument is valid for any number of colors, so your condition is the correct one for any number of colors as well.