Paths walks and cycles

What is a walk in a graph?

A walk is a sequence of vertices connected by edges, where vertices and edges can repeat.

What is a trail?

A trail is a walk where no edge is repeated.

What is a path?

A path is a walk where no vertex or edge is repeated.

What is a simple path?

A simple path is another term for a path with no repeated vertices or edges.

What is a closed path?

A closed path starts and ends at the same vertex.

What is a circuit?

A circuit is a closed trail — it starts and ends at the same vertex and doesn’t repeat edges.

What is a cycle?

A cycle is a closed path where only the first and last vertices are the same and no other vertices repeat.
💡 Visual: Think of a round trip where you visit different cities and come back home once.

What is the length of a path?

The length is the number of edges in the path.

What is the difference between a trail and a path?

A trail doesn’t repeat edges, while a path doesn’t repeat vertices.

What is an Euler trail?

An Euler trail uses every edge exactly once.

What is an Euler circuit?

An Euler circuit is an Euler trail that starts and ends at the same vertex.
💡 Example: Drawing a figure without lifting your pencil and ending where you started.

What is a Hamiltonian path?

A Hamiltonian path visits every vertex exactly once.

What is a Hamiltonian cycle?

A Hamiltonian cycle visits every vertex exactly once and returns to the starting point.