|
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.
| 
![$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ A \ar@{-}[r] & B \ar@{-}[d] \ D \ar@{-}[u] & C \ar@{-}[l] } } \end{xy}$](http://images.planetmath.org:8080/cache/objects/1731/l2h/img8.png "$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ A \ar@{-}[r] & B \ar@{-}[d] \ D \ar@{-}[u] & C \ar@{-}[l] } } \end{xy}$")
![$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ G \ar[r] \ar[d] & H \ar[d] \ar[l] \ J & I \ar[l] } } \end{xy}$](http://images.planetmath.org:8080/cache/objects/1731/l2h/img19.png "$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ G \ar[r] \ar[d] & H \ar[d] \ar[l] \ J & I \ar[l] } } \end{xy}$")