Graphs, Connected Graphs, Components

Connected Graphs, Components

A graph is connected if for every pair of vertices v1 and v2, there is a path starting at v1 and ending at v2. A digraph is strongly connected if every pair of vertices has a connecting path. A digraph is weakly connected if its symmetric closure (the implied graph) is connected.

A component is a maximal connected subgraph. A connected graph has only one component.

There is a path from v1 to v2 iff there is a walk. By definition, any path will serve as a walk. If a walk never repeats a vertex, it will serve as a path. Otherwise, we can delete the portion of the walk between two instances of the repeated vertex, making a shorter walk. The shortest walk is a path. Defining connectivity in terms of walks rather than paths yields the same concept.

To say that a graph is connected is an oversimplification that often proves inadequate. When discussing the "strength" of a graph's connectivity, several important terms are used.

A bridge is an edge that, when removed, disconnects the graph.

A block is a maximal subgraph that contains no bridges.

A cutpoint is a vertex that, when deleted, disconnects the graph.

A cutset is a minimal set of vertices that, when deleted, disconnects the graph.

The connectivity of a graph is the number of vertices in its minimum cutset. By definition, the connectivity of a disconnected graph is 0. The connectivity of a cycle is always two, while the connectivity of Kn is n.

The line connectivity of a graph is the minimum number of lines that, when deleted, disconnects the graph. The line conectivity of a block containing more than two vertices is at least two. This is because a block has no bridge.

A graph is k connected if its connectivity is at least k, and l line connected if its line conectivity is at least l.