[Math] When does a closed walk not have a cycle

graph theory

Closed walk: sequence of vertices and edges where the first vertex is also the last
Cycle: closed walk where all vertices are different (except for first/last)

I can't think of an example where a closed walk is not a cycle because the cycle can just omit the part not needed.

For example in the graph bellow A,B,C,E,B,D,A is a closed walk and A,B,D,A is a cycle. Am I thinking of this wrong, does a cycle mean there is no repeating parts anywhere in the graph?

example graph

Best Answer

Consider the walk $A \rightarrow D \rightarrow A$ in your graph above. This ends up at the node you started from, but does not contain a cycle. The definition of a cycle is a path that starts and ends at the same vertex without repeating any edges. Note that a cylce may have repeated vertices, but a simple cycle doesn't, so $A \rightarrow D \rightarrow B \rightarrow E \rightarrow C \rightarrow B \rightarrow A$ is a cycle but not a simple cycle due to the repetition of vertex $B$

Related Question