Graphs, Walks Paths and Trails

Walks Paths and Trails

A walk is a sequence of vertices in a graph or digraph, such that every edge v_i→v_i+1 exists.

A path is a walk that does not repeat a vertex.

A cycle is a path that includes the edge v_n→v₁.

a trail is a walk that never repeats an edge. If v₁ = v_n, we have a cyclic trail. A cyclic trail is distinctly different from a cycle; the former never repeats an edge, and the latter never repeats a vertex, save the first/last vertex.

The distance between two points is the length of the shortest path.

The diameter of a graph is the longest distance between two points.

The girth of a graph is the length of the shortest cycle.

The circumference of a graph is the length of the longest cycle.