1.4 Paths and Connected Graphs

A path is a sequence of edges, e.g. $(v_{1},v_{2}),(v_{2},v_{3}),\cdots,(v_{{n-1}},v_{n})$. This path connects vertices $v_{1}$ and $v_{n}$. The path may also be represented by the vertex sequence $v_{1},v_{2},v_{3},\cdots,v_{{n-1}},v_{n}$. The path begins at vertex $v_{1}$ passes through vertices $v_{2},v_{3},\cdots,v_{{n-1}}$ and ends at vertex $v_{n}$.

The number of edges that comprise a path is its length. A path is simple if all of the vertices on a path are distinct (with the possible exception of the first and last vertices).

If some path connects each pair of vertices in $G$, then $G$ is a connected graph.

Connected digraphs are classified as either weakly connected or strongly connected. A strongly connected digraph has a directed path that connects all the vertices in the graph. All the vertices of a strongly connected digraph must have an in-degree of at least one.

A weakly connected digraph has has an undirected path that connects all the vertices in the graph. All the vertices of a weakly connected digraph must have either an in-degree or out-degree of at least one.