A finite alternating sequence of vertices and edges, which begins and ends with a vertex, so that each edge is incident with the vertices preceding and following it.
Trail
A walk with no repeating edges. Vertices may repeat.
Circuit
Aka. closed trail. A trial with the same starting and ending vertices. A walk with no repeating edges, that start and end in the same vertex.
Path
A trail with no repeating vertices (except the starting and ending pair). A walk with no repeating edges or vertices.
Cycle
A closed path. Starts and ends in the same vertex. No repeating vertices and no repeating edges.
All cycles with the same vertices and edges, are considered a single cycle, even if written in a different order.
Length of a cycle is defined as:
- number of edges in unweighted graph
- sum of weights of edges in weighted graph
Euler Path
A trail that traverses every edge. No repeating edges. Vertices may repeat.
An Eulerian path cannot exists if more than 2 vertices have ann odd degree.
A connected graph has an Eulerian path if and only if it has exactly 0 or 2 vertices of odd degree.
Euler Circuit
A closed Euler path. Starts and ends in the same vertex.
Hamiltonian Path
Aka. traceable path. A path that contains every vertex of the graph. No repeating edges and no repeating vertices.
Hamiltonian Cycle
Aka. Hamiltonian Circuit. A closed Hamiltonian path.
Comparison
| - | Repeating Vertices | Repeating Edges | Same Start and End |
|---|---|---|---|
| Walk | Yes | Yes | No |
| Closed Walk | Yes | Yes | Yes |
| Trail / Euler Path* | Yes | No | No |
| Circuit (Closed Trail) / Euler Circuit* | Yes | No | Yes |
| Path / Hamiltonian Path** | No | No | No |
| Closed Path / Hamiltonian Circuit** | No | No | Yes |
*must traverse every edge. **must traverse every vertex.