When does a closed walk not have a cycle?

$\begingroup$

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?

$\endgroup$ 1

1 Answer

$\begingroup$

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$

$\endgroup$ 4

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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