No odd-length cycles imply no odd-length closed walks - proof by contradiction

542 Views Asked by At

I wanted to ask for feedback on a proof I did. It took me some time and reading a few different resources to grok what's going on in that proof, so I wanted to formulate my understanding in a proof in my own words.


Claim: If a graph $G$ does not contain any cycles with odd length, then $G$ does not contain any closed walks with odd length.

Proof, by contradiction: Assume for purpose of contradiction that $G$ does not contain any cycles with odd length, but indeed does contain a closed walk with odd length.

We assume $w = v_0, v_1, ..., v_k$ of length $k$ to be the shortest closed walk of odd length in $G$.

Since there are no odd length cycles in $G$, $w$ can't be a cycle either and has to be a closed proper walk. By the definition of proper walks, $v_i = v_j$ for some $0 \le i < j < k$ in $w$:

$$w = v_0, ..., v_i, ..., v_j, ..., v_k$$

Let the number of edges from $v_i$ to $v_j$ be $n$.

Now we can split $w$ into two closed walks

$$w' = v_i, ..., v_j$$ of length $n$ and $$w'' = v_0, ..., v_i, v_{j+1}, ..., v_k$$ of length $k - n$.

Since the length $k$ of $w$ was odd, either $n$ is odd or $k-n$ is odd. This shows that we can find a shorter closed walk with odd length in $G$ than $w$, contradicting our assumption that $w$ was the shortest closed walk.

1

There are 1 best solutions below

1
On BEST ANSWER

It's basically good, but since a cycle is a special case of closed walk and that a walk don't have to be closed you should probably have written:

Since there are no odd length cycles in $G$, $w$ can't be a cycle either and has to be a closed proper walk. By the definition of proper walks, $v_i=v_j$ for some $0\le i<j<k$ in $w$

That is both tell that the walk is both closed and proper (that is non-cycle).

Also probably a typo: $w''$ should be $v_0,\dots,v_i,v_{j+1},\dots,v_k$ (otherwise both are not shorter than $v$).