A paper is now available describing it: Eulerian Edge refinements, geodesics, billiards and sphere coloring [PDF].
The paper is now on the arXiv.
You can grab from the LaTeX source the Mathematica code featured at the end of the article.Surfaces without boundary
The Euler-Hierholzer theorem tells that a graph admits an Eulerian cycle, if and only if all vertex degrees are even. One calls therefore a graph in which all vertex degrees are even “Eulerian”. Given a finite simple graph G and an edge e=(a,b) in G, an edge refinement over e adds a new vertex e between a and b and connects it to $S(x) \cap S(y)$. For a 2-graph, a graph with the property that all unit spheres $S(x)$ are circular graphs with 4 or more vertices, we have the following theorem
| Theorem I: For any 2-graph G, there exists a sequence of edge refinements which render the graph Eulerian. |
This was mentioned in this paper on graph coloring already, but only for 2-spheres. The constructive proof can be done by “geodesic cutting”:
Proof. Start with a vertex y of odd degree. Chose a vertex $x \in S(y)$. Now, there are two adjacent vertices (a,b) on S(y) opposite to y. The reason is that S(y) has an odd number of elements preventing a single “antipodal point to exist. Now make an edge refinement at (a,b) by adding a new vertex c in between (a,b) and connecting to all vertices {y,z} and continue the path through this edge to the next point z. The path is now x,y,c,z. Now continue to cut like this until we reach an other vertex which has odd vertex degree, then stop. This has reduced the number of odd degree vertices by 2. The reason why this works is that we can never cover any edge twice so that we eventually reach a second vertex of odd degree. The Euler Handshake formula shows that the number of odd degree vertices is even.
The process of rendering a graph Eulerian can also be implemented as a solitary game. One has to work carefully as during the process of cutting, the game becomes more difficult. It is like the “Rubik cube fighting back” (“Skyfall”). But the theorem tells that we can always win the game. Because of this, we should use the rule that a player can not take a cut back also as this is a genuine property of cuts. The theorem assures that the player can still win the game at any time. It just gets more and more difficult. For a computer it is no problem at all as the above geodesic cutting algorithm does the job nicely.
Surfaces with boundary
If we allow the 2-graph to have boundary, we still can ask whether it is possible to render the graph Eulerian. We ask the refinements to happen from the interior. Again, we can achieve that with edge cuts in the interior of the disk:
| Theorem II: A 2-ball G can be rendered Eulerian with interior edge refinements if and only if the boundary length is divisible by 3. |
Proof. (Update: August 23, 2018) Here is a better proof what is in the preprint: Take a 2-ball G. We have given procedures to switch so that odd and even degree vertices switch and to annihilate two if three are in a unit ball of one of them. This allows us to move all the odd degree vertices to the boundary and reduce so that only 2 are left. We have to show that we can reduce the last two if and only if the boundary length is divisible by 3. The necessity is easy as this implies that the canonical 3-coloring induces a periodic coloring of the boundary. For the sufficiency we have to show that if the boundary length is divisible by 3, then we can eliminate the last two remaining odd degree vertices. Here is the new approach: we proceed with induction on the length of the boundary of G. For n=3, we have a triangle without any odd degree vertices so that things are already eliminated there. Take now a table G with arbitrary boundary and edge refine until only 2 vertices are left. Now pick one of the odd degree vertices x at the boundary. As the degree is odd, there is an edge e=(x,x’) which is in the middle ,halfing the half circle S(x). Start a geodesic in this direction. It will flow nicely through the interior as all interior vertices have even degree. Let y be the boundary point it reaches first. Stop the geodesic there. This cuts the table into two smaller tables U,V and no odd degree vertex is at the new cut x -> y dividing the tables. Assume V contains the second odd degree vertex of G.  Now as in both tables U,V, the vertex x has even degree, the vertex y must be an odd vertex in V and an even vertex in U. Now look at the three cases of $|\delta G|$. If this is NOT divisible by 3, then by induction (U is a smaller without odd degree vertices), U has boundary length divisible by 3 and as the boundary of G was not divisible by 3, V also has boundary length not divisible by 3 (just check the modular arithmetic possibilies) . So, also by induction, we can annihilate the two odd degree vertices y and z in V.   In the second case, if $\delta G|$ is divisible by 3, then as the table U has still no odd degree vertices (z can not be alone), U must have a boundary length divisible by 3. But that implies that V has boundary length NOT divisible by 3 (again just check the modular possibilites). We know now what to do: just start an other geodesic at y, splitting the vertex there and cutting V. As the same applies to V what was before applying for G, we see that this division produces two tables P,Q which both have length divisible by 3 and by induction can be reduced. After having tables P,Q which are without odd degree vertices, remove the split. This produces a table V which can not be reduced and features two particles. Make further edge refinements until the edges are at the original points x,y. But now, removing the division line splitting G into U,V removes these odd degree vertices and leaves a clean table G.
As a consequence if we have simple curve in a 2-sphere for which all vertices have even degree and the length is not divisible by 3, then there is an odd degree pair on one side, there must be also an odd degree pair on the other side.
There are various reasons why Eulerian graphs are interesting: an Eulerian disk or sphere can be colored with the minimal number 3 of colors. It admits a billiard or geodesic flow. Furthermore, the Barycentric refinement of a disk or sphere is always Eulerian.
Like in any game, we want also a fast strategy. There are two possibilities
- Given two neighbors (a,b), where a is odd and b is even, it is possible switch that b is odd and a is even. This property allows us to move the odd ones around so that they are in distance 1 or 2 to each other.
- Given an odd degree vertex c, and two a,b in S(c) which are not adjacent, it is possible to switch the parity of both a and b. This allows us to kill two of three neighboring odd vertices.
Together, we can now first put all the odd ones on a cycle and then move them together until we have one alone or two alone. One alone can not happen as the number of odd ones is even.
Assume we end up with a single pair of odd points. We can not give a local procedure to remove those because as it turns out, there are two type of odd degree cycles and only pairs of different kind can annihilate. For example, if they are neighbors or if they are 2 apart on S(c) where the two ab half circles are odd. An odd-odd cycle is an obstacle to kill the pair. The number of odd-odd cycles is even however. As if a curve bounds an Eulerian disk, the total number of edge degrees is divisible by 2. We still have to show that two odd degree vertices are left on the boundary and everything else is Eulerian, it can be canceled off.
Think of an odd degree vertex as a particle. Assume we have only two odd degree vertices a,b. There is an Eulerian path which starts at a and ends at b. Assume (a,b) is an edge, then removing this edge produces an Eulerian graph for which an Eulerian cycle exists.
Lets play the game on the plane and assume we have Given two adjacent odd degree vertices, one with degree 5 and one with degree 7.
We can get such a situation from the flat hexagonal lattice by flipping a diagonal in a square. We can ask ourselves, whether it is possible to use edge refinements to recover an Eulerian situation. The answer is no! If it were possible, then it would also be possible on a sufficiently large torus and we know that this is not possible.
By handshake, we have an even number of particles. It appears now that we have two different type of defect vertices. They somehow live on two different sides. We can only cancel off two of different kind. Two neighboring odd degree vertices can not be canceled off.
| Theorem: a disc D can become Eulerian with interior edge refinement if and only if its boundary length is divisible by 3. |
We see here an example of a 2-disk D. The odd degree vertices are blue. We play the Euler game to remove the odd degree vertices. We do not succeed here. Indeed, since the boundary length is not divisible by 3, the Euler game is not winnable.
Example: Wheel graphs of length 3k all can be made Eulerian within the wheel. We have to show two things: for a disk with a 3k boundary, we can refine if we can refine, then the boundary has length 3k. The charge of a disk B is defined as mod( dB,3) \in {-1,0,1}. So, we have neutral disks, positively and negatively charged disks. For disks with more than one interior point, we can move all odd degree vertices inside.
