Connected Graphs, Components

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.