2
$\begingroup$

Note: this is homework. Please do not give a complete answer.

I've had a brief introduction in graph theory. We have been given to find a shortest cycle visiting all edges and starting and finishing in $(0,0)$ in the following graph:

enter image description here

Since there are vertices like $(0,1)$ with an odd degree, there can't exist an Eulerian cycle. Therefore, the length has to be longer than 31, which is the amount of edges in the graph.

It's quite easy to find a cycle with length 38 by trying, visiting seven edges twice, however, I can't think of a way to prove that this actually is the shortest possible cycle.

I'm thinking: there are ten vertices with an odd degree, to which at least one edge that is visited twice must be connected. If we would take these edges as ((0,1),(0,2)), ((0,2),(0,3)), ((1,0),(2,0)), ((1,4),(2,4)), ((3,1),(3,2)), ((3,2),(3,3)) - that is, the edges between points with an odd parity -, that creates another problem: Now, the vertices (0,2) and (3,2) have already been visited twice, but the edges ((0,2),(1,2)) and ((2,2),(3,2)) have not been used yet. Now these edges would need to be visited twice as well, so there are at least 8 edges that have to be visited twice, making this a longer cycle than the one of length 38.

However, am I right in thinking that this at least means that the shortest cycle has a minimum length of 31+6=37? And how can I proceed in finding the shortest path, if it has length 37, or in proving that length 37 isn't possible?

I also noticed that this is a bipartite graph. We could colour the vertices $(p,q)$ for which $2\mid p+q$ blue, and the others red. I'm not sure if this is useful, or how to proceed from this, though.

$\endgroup$
  • $\begingroup$ I couldn't create the tag eulerian-cycle, but maybe someone with more rep could edit that in? $\endgroup$ – user63495 Jan 8 '15 at 18:04
  • $\begingroup$ There are 10 vertices of odd degree, not 8. Each of those vertices must be visited at least twice. $\endgroup$ – Leen Droogendijk Jan 8 '15 at 18:28
  • $\begingroup$ @LeenDroogendijk right, thanks, I edited the question. $\endgroup$ – user63495 Jan 8 '15 at 18:29
  • $\begingroup$ I am not sure if you are aware of it, but this is just an instance of the familiar Chinese postman problem. $\endgroup$ – Leen Droogendijk Jan 8 '15 at 18:33
  • $\begingroup$ @LeenDroogendijk I wasn't aware of that, thanks. The wikipedia is quite ununderstandable for me, but ModdedBear explained it in simple words already in his answer. Thanks! :) $\endgroup$ – user63495 Jan 8 '15 at 18:39
0
$\begingroup$

You want to find a multigraph that contains the graph in question and has all vertices with even degree. Another way to think of it is that you have to add a graph to the one you allready have in which the only vertices of odd degree are the ones which have odd degree in the original graph.


Seeing Leon Droogendijik comment what I told you is what wikipedia says, you need to find the multigraph with the least edges on the same vertex set that is a supergraph of the graph in question. To solve this problem you need to find the smallest multigraph whose only odd vertices are the vertices that are odd in your graph.

$\endgroup$
  • 1
    $\begingroup$ I got the minimum cycle length was $38$, $7$ edges where doubled $\endgroup$ – Jorge Fernández Hidalgo Jan 8 '15 at 18:33
  • $\begingroup$ Yeah, what you tell me is what wikipedia tells me, but this is a lot clearer to me than the wiki :) thank you very much, this has helped a lot, I will now be able to finish on my own. $\endgroup$ – user63495 Jan 8 '15 at 18:38
1
$\begingroup$

If you double some of the edges, you can reduce the number of nodes with odd degree. For Eulerian path, you'd need to find he least number of edges you can add to make all but two of the nodes of even degree. For the cycle, you need to elimiate all odd nodes by add such edges.

There's clearly a solution for 7 added edges, as you say, so demonstrating that neither 5 nor 6 are feasible is required. If four adjacent odd nodes are connected, the remaining two nodes (eg. (0,3) and (3,3)) require 3 additional edges to connect; If three adjacent nodes are connected then both of the remaining pairs require at least two edges each to connect. In both cases 7 is the minimum.

$\endgroup$
  • $\begingroup$ Thanks, I suppose that would be four - but why the 'but two'? $\endgroup$ – user63495 Jan 8 '15 at 18:26
  • 2
    $\begingroup$ I think he thought you needed an eulerian path $\endgroup$ – Jorge Fernández Hidalgo Jan 8 '15 at 18:27
  • $\begingroup$ Start node and end node do not need to be even degree $\endgroup$ – Joffan Jan 8 '15 at 18:27
  • $\begingroup$ I'm sorry, I forgot to mention an essential point, that you have to start and end in (0,0). I already mentioned that this is about a cycle, not a path, so in any case the start and end node would be the same and should have an even degree. $\endgroup$ – user63495 Jan 8 '15 at 18:27
  • $\begingroup$ Right, I read "visiting all edges" and missed "cycle". However the principle stands, just needs extension to remove all odd nodes. $\endgroup$ – Joffan Jan 8 '15 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy