Thread: Eulerization

So I'm a little desperate at this point. I've drawn like 5 pages of pictures and I just cant seem to see a pattern. Any insight would be awesome.

The problem:
Eulerize a grid graph G(m,n) for all m, n greater than or equal to 2.

...in other words, what is the fewest number of edges you need to duplicate so that the new graph has an Eulerian circuit.

G(3,3)

O--------O--------O
|
O--------O--------O = 4 added edges to make circuit
|
O--------O--------O

....sorry cant make grid graphs very well on a computer

Originally Posted by luckyNUM7

So I'm a little desperate at this point. I've drawn like 5 pages of pictures and I just cant seem to see a pattern. Any insight would be awesome.

The problem:
Eulerize a grid graph G(m,n) for all m, n greater than or equal to 2.

...in other words, what is the fewest number of edges you need to duplicate so that the new graph has an Eulerian circuit.

G(3,3)

O--------O--------O
|
O--------O--------O = 4 added edges to make circuit
|
O--------O--------O

....sorry cant make grid graphs very well on a computer

If I'm understanding properly, you are adding edges to change the simple undirected grid graph G(m,n) into an undirected multigraph with an Eulerian circuit.

If this is the case then you need to find an optimal way to add edges such that every vertex has even degree, which is a necessary and sufficient condition for an Eulerian circuit's existence.

Were you working along these lines and unable to spot a pattern? Or were you working along some other lines?

Yes that is correct. And it needs to be for any m and n. I was working along the lines that you had stated and still wasn't able to find a pattern.

so a graph G(3,3) would have 3 horizontal rows and 3 vertical columns. And a graph G(5,4) would have 5 rows and 4 columns...and so on.

...i guess i just need a little nudge to find a sufficient pattern.

any ideas?

Originally Posted by luckyNUM7

Yes that is correct. And it needs to be for any m and n. I was working along the lines that you had stated and still wasn't able to find a pattern.

so a graph G(3,3) would have 3 horizontal rows and 3 vertical columns. And a graph G(5,4) would have 5 rows and 4 columns...and so on.

...i guess i just need a little nudge to find a sufficient pattern.

any ideas?

Well if m and n are both even and greater than or equal to 4, I claim that the answer is m + n - 4.

Consider the starting graph, G(m, n). There are three types of vertices, "internal" which have degree 4, "edge" which have degree 3, and "corner" which have degree 2. Only the edge vertices pose an immediate problem.

If a side has an even number of vertices greater than 4, just duplicate every other edge along that side (don't touch any edges that are connected to corner vertices), and the edge vertices will now all have degree 4. For side length s, this results in (s/2)-1 extra edges.

With m and n even and >= 4, we have 2*((m/2)-1)+2*((n/2)-1) = m + n - 4.

Other cases seem to be more complicated. But does that help?

Well the original problem was m and n greater than or equal to 2, but its fine.

But then how do you explain G(3,3) and G(4,4)? In G(3,3) if you duplicate an edge and have it connect form each side vertex to a corner, the answer is 4 added edges for eulerization. In G(4,4), if you link up each side vertex (there are two on each side) then the answer is also 4?

Originally Posted by luckyNUM7

Well the original problem was m and n greater than or equal to 2, but its fine.

But then how do you explain G(3,3) and G(4,4)? In G(3,3) if you duplicate an edge and have it connect form each side vertex to a corner, the answer is 4 added edges for eulerization. In G(4,4), if you link up each side vertex (there are two on each side) then the answer is also 4?

The case of having m, n both even and >= 4 accounts for about 25% of all (m,n). G(4,4) falls under this case and results in 4 + 4 - 4 = 4.

I have not classified the case when at least one of m or n is odd, and it might take a decent amount of work to solve. But I can give you an upper bound: if you duplicate every "internal edge" then you will have an Eulerian graph. An internal edge means that at least one of its vertices is internal. You will get graphs akin to these. The upper bound is then (m-2)*(n-1)+(m-1)*(n-2) = mn - 2n - m + 2 + mn - n - 2m + 2 = 2mn - 3(m+n) + 4.

After making some more diagrams, I can improve my upper bound in the case that m and n are both >= 3 and exactly one of them is odd.

See attached diagram for (m,n) = (4,5).

Possibly this is already optimal; I don't know.

EDIT: Just to be clear, I interpreted your original post to mean that we are only allowed to add new edges between adjacent vertices. That is, we can't draw new edges diagonally or anything of the sort. Is that a correct interpretation?