1.4 Paths and Connected Graphs
A path is a sequence of edges, e.g. . This path connects vertices and . The path may also be represented by the vertex sequence . The path begins at vertex passes through vertices and ends at vertex .
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 , then 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.