3
$\begingroup$

I am trying to prove what's on the title. I have been working on it for some time already and the problem I have is that I can't seem to prove that the cycle I get at the end is of odd length.

Here are the conclusions I reached, which I am not sure at all are correct:

If G contains a closed walk of odd length (let's say a u-v walk), then it contains 2 u-v walks, one of even length and another one of odd length so that when added up they give an odd number. Then for every of these u-v walks, we can obtain a u-v path by removing all the repeated fragments of the walk.

We are left now with 2 paths. These two paths might form a cycle or not.

In the case they do form a cycle, we are done (however I know nothing about the length of such cycle).

In the case they do not form a cycle, remove all xy edges s.t. xy belongs to both paths. We will remove an even number of edges before we reach the cycle; but then again, I can't tell the parity of the length).

Thanks a lot!

$\endgroup$
7
$\begingroup$

If you have a closed path $aa$, so the end point is equal to the begin point. If this is the only point that is reached twice you are done.

If there is another point that is reached twice say $v$ then you can make two new closed paths $vv$ were one goes to $a$ and back and the other is the rest. One has to be of odd length. Repeat this argument with the odd length closed walk until you have a cycle.

$\endgroup$
  • $\begingroup$ But how can you assure the length of the cycle is an odd number? And, is my proof correct or wrong? $\endgroup$ – Ruben Mar 8 '14 at 12:34
  • $\begingroup$ You only go further with closed walks that have odd length. Then eventually a closed walk will be a cycle and then it is by construction odd. $\endgroup$ – Kaladin Mar 8 '14 at 12:41
  • $\begingroup$ in your prove you remove edges that coincide. That does give you to paths but they could be disjoint. The you can still say that one of the path has to be odd. Because the edges you remove have been traveled an even number of times. $\endgroup$ – Kaladin Mar 8 '14 at 12:46
  • $\begingroup$ But when i remove the common edges, I consider two u-v paths, so they should not be disjoing, right? $\endgroup$ – Ruben Mar 8 '14 at 16:25
  • $\begingroup$ What I thought when reading you proof was: when you have 2 $uv$ paths for example $u-u_1- u_2- u_3- u_4- v$ and $u- u'_1- u_2- u_3- u'_4- v$ if these are your two paths and when you remove common edges so $u_2u_3$ you get the paths $u -u_1 -u'_1- u$ and $v- u_4- u'_4- v$ these are disjoint. $\endgroup$ – Kaladin Mar 8 '14 at 16:30
1
$\begingroup$

The result is clearly true for the shortest possible closed odd walk, namely a loop (i.e. a cycle of length 1). Make the inductive hypothesis that it holds for all closed odd walks shorter than the given one.

If no vertices are repeated in the walk, other than the first and last, then the walk itself is an odd cycle. Otherwise, let the walk be $v_0v_1\dots v_rv_0$, of odd length $r+1$, and let $j$ be the smallest number such that $v_j$ occurs again later in the walk, i.e. $v_j = v_k$ where $j < k \leq r$.

The given walk is the union of the two closed walks $v_0v_1 \dots v_jv_{k+1} \dots v_rv_0$ and $v_jv_{j+1}v_{j+2} \dots v_k$. The sum of the lengths of these tow walks is odd, so one of them is a closed walk of shorter odd length than the original one. By the hypothesis this walk contains an odd cycle, which is contained in the given walk. The result follows by induction on the length of the walk. $\square$

$\endgroup$
  • 1
    $\begingroup$ I don't think you can use induction like this (at least the base case), because the graph might not have a loop. $\endgroup$ – WeakestTopology Dec 2 '17 at 18:36
  • $\begingroup$ Yes you are right, however you can just start with the base case with length of the closed odd walk equals 3, since that must be by definition a cycle. $\endgroup$ – Marco Bellocchi Dec 29 '17 at 14:39

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.