[Math] Graph theory – Shortest closed walk is a cycle

directed graphsgraph theory

So I'm trying to prove the lemma:
"The shortest positive length closed walk through a vertex is a cycle."

Defs: A closed walk is a walk that begins and ends at the same vertex. A cycle is a positive length closed walk whose vertices are distinct except for the beginning and end vertices.

So far I have:

Proof: If there is a closed walk from u to v, then there must be a positive minimum length walk w, from u to v. We claim w is a cycle.
To prove this claim, suppose to the contrary that the shortest positive length closed walk through a vertex is not a cycle. Meaning some vertex (x) is not repeated within this closed walk u to v and there is another vertex (y),

 w = e (merge x) f (merge y) g

for some walks e, f, g where f is positive.
If we delete f then.. (this is where I am stuck.)

I'm doing this proof based off another, to which book said they would be essentially the same but I'm not sure. Where am I going wrong?
Other proof:

Other Lemma

Best Answer

Well, to be clear here, we first note that all walks here have to be non-lazy and also be nonbacktracking as in if $W=x_1x_2\ldots x_r$ then $x_j \not \in \{x_{j+1},x_{j+2}\}$ for all $j$. Otherwise a walk that traverses an edge in each direction (or stays at the same vertex) is closed but is not a cycle.

Next, suppose $G$ is a path $P=u_0\ldots u_r$ with $r+1$ vertices plus a cycle $C$ that intersects $P$ at precisely $u_r$. Then the shortest closed non-lazy nonbacktracking walk in $G$ that contains the vertex $u_0$ is not a cycle, you need to walk from $u_0$ to $u_r$, go around the cycle $C$, and then come back to $u_0$. The shortest walk in $G$ overall is a cycle though; in fact it is $C$. This shortest walk does not contain $u_0$.

Anyway, let $G$ be a graph. Then the shortest closed non-lazy nonbacktracking walk in $G$, if such a walk exists, is a cycle.

Proof Sketch [make sure you see each step]: Let $W = x_0x_1x_2\ldots x_t$ be a shortest-length closed nonbacktracking walk. Then by the fact that $W$ is closed $x_0=x_t$. Suppose that $W$ is not a cycle. Then there are integers $i'$ and $j'$; $i'<j'$ s.t. $j'-i' < t$, and $x_{i'}=x_{j'}$. Then $W'=x_{i'}x_{i'+1}\ldots x_{j'}$ [i.e., $W$ minus the first $i'-1$ vertices and the last $t-j'$ vertices of $W$] is a closed walk and is shorter than $W$. Contradiction.

Related Question