In mathematics and computer science the connectivity of graphs is one of the basic concepts of graph theory. It is closely related to the concept of path.

In network theory we are often interested how many connections (edges) in the network are allowed to fail before two nodes (vertices) become disconnected. Menger's theorem and Fulkerson's theorem provide characterizations of this problem.

By adding weights to the edges of the graph we are able to consider network flow problems which allow a finer discussion of connectivity.

Checking if a graph is connected, or even its number of connected components, is a very easy problem that can be solved in deterministic logarithmic space (see SL).

Contents

1 Connections 2 Cuts 3 Examples 4 Properties 5 See also

Connections

Given an undirected graph, two vertices u and v are called connected if there exists a path from u to v. Otherwise they are called disconnected. The graph is called connected graph if every pair of vertices in the graph is connected.

Cuts

A vertex cut for two vertices u and v is a set of vertices whose removal from the graph disconnects u and v. A vertex cut for the whole graph is a set of vertices whose removal renders the graph disconnected. The vertex connectivity κ(G) for a graph G is the size of minimum vertex cut. A graph is called k-vertex-connected if its vertex connectivity is k or greater.

The same concept can be defined for edges.

An edge cut for two vertices u and v is a set of edges whose removal from the graph disconnects u and v. A edge cut for the whole graph is a set of edges whose removal renders the graph disconnected. The edge connectivity κ'(G) for a graph G is the size of the minimum edge cut. A graph is called k-edge-connected if its edge connectivity is k or greater.

Examples

• The vertex and edge connectivities of a disconnected graph are both 0
• A connected graph is 1-connected by definition
• A complete graph is maximally connected; if it has n vertices, its edge connectivity is n
• A tree is minimally connected; its edge connectivity is 1

Properties

• Connectedness is preserved by graph homomorphisms.
• If G is connected then the line graph L(G) is connected too.
• A graph is k-vertex-connected if and only if it contains k vertex independent paths between any two vertices.
• A graph is k-edge-connected if and only if it contains k edge independent paths between any two edges.
• Given a k-vertex-connected graph G then for every set of vertices U there exists a cycle in G containing U
• Given a connected graph the distance between two vertices u and v is equal to the number of pairwise disjunct edge cut sets which separate u and v.

See also

• Menger's theorem