path
\\xyoptionall
A path in a graph is a finite sequence of alternating vertices and edges, beginning and ending with a vertex, such that every consecutive pair of vertices and are adjacent and is incident
with and with . Typically, the edges may be omitted when writing a path (e.g., ) since only one edge of a graph may connect two adjacent vertices. In a multigraph
, however, the choice of edge may be significant.
The length of a path is the number of edges in it.
Consider the following graph:
Paths include (but are certainly not limited to) (length 3), (length 4), and (length 12). is not a path since is not adjacent to .
In a digraph, each consecutive pair of vertices must be connected
by an edge with the proper orientation
; if is an edge, but is not, then is a valid path but is not.
Consider this digraph:
, , and are all valid paths. is not a valid path because and are not connected. is not a valid path because the edge connecting to has the opposite orientation.