Connectedness in undirected graphs

An undirected graph is called connected if there is a path between every pair of distinct vertices of the graph.

Example.

The graph G is connected, since for every pair of distinct vertices there is a path between them. However, the graph H is not connected. For instance, there is no path in H between vertices a and d.

Theorem 1. There is a simple path between every pair of distinct vertices of a connected undirected graph.

Proof: Let u and v be two distinct vertices of a connected undirected graph G = (V, E). Since G is connected, there is at least one path between u and v. Let x₀, x₁, …, x_n, where x₀ = u and x_n = v, be the vertex sequence of a path of least length. This path of least length is simple. To see this, suppose it is not simple. Then x_i = x_j for some i and j with . This means that there is a path from u to v of shorter length with vertex sequence x₀, x₁, …, x_i–1, x_j, …, x_n obtained by deleting the edges corresponding to the vertex sequence x_i, …, x_j–1.

A graph that is not connected is the union of two or more connected subgraphs, each pair of which has no vertex in common. These disjoint connected subgraphs are called the connected components of the graph.

Sometimes the removal of a vertex and all edges incident with it produces a subgraph with more connected components than in the original graph. Such vertices are called cut vertices (or articulation points). The removal of a cut vertex from a connected graph produces a subgraph that is not connected. Analogously, an edge whose removal produces a graph with more connected components than in the original graph is called a cut edge or bridge.

Example. Find the cut vertices and cut edges in the graph G.

Solution: The cut vertices of G are b, c and e. The removal of one of these vertices (and its adjacent edges) disconnects the graph. The cut edges are {a, b} and {c, e}. Removing either one of these edges disconnects G.

Date: 2015-01-02; view: 1184