In graph theory, a connected graph is said to be -vertex-connected (or -connected) if it has more than vertices and remains connected whenever fewer than vertices are removed.

The vertex-connectivity, or just connectivity, of a graph is the largest for which the graph is -vertex-connected.

Definitions

A graph (other than a complete graph) has connectivity k if k is the size of the smallest subset of vertices such that the graph becomes disconnected if you delete them. In complete graphs.

An equivalent definition is that a graph with at least two vertices is k-connected if, for every pair of its vertices, it is possible to find k vertex-independent paths connecting these vertices; see Menger's theorem . This definition produces the same answer, n1, for the connectivity of the complete graph Kn.

A k-connected graph is by definition connected; it is called biconnected for k ≥ 2 and triconnected for k ≥ 3.

Applications

Components

Every graph decomposes into a disjoint union of 1-connected components. 1-connected graphs decompose into a tree of biconnected components. 2-connected graphs decompose into a tree of triconnected components.

Polyhedral combinatorics

The 1-skeleton of any k-dimensional convex polytope forms a k-vertex-connected graph (Balinski's theorem). As a partial converse, Steinitz's theorem states that any 3-vertex-connected planar graph forms the skeleton of a convex polyhedron.

Computational complexity

The vertex-connectivity of an input graph G can be computed in polynomial time in the following way of nonadjacent nodes to disconnect, using Menger's theorem is the number of pairwise vertex-independent paths between them, encode the input by doubling each vertex as an edge to reduce to a computation of the number of pairwise edge-independent paths, and compute the maximum number of such paths by computing the maximum flow in this graph corresponds, by the integral flow theorem.

Properties

Let .

• contains a cycle

• lie on a common cycle.

The cycle space-connected graph is generated by its non-separating induced cycles.

k-linked graph

vertices is called -linked-connected.

-linked.

See also

• k-edge-connected graph

• Connectivity (graph theory)

• Menger's theorem

• Structural cohesion

• Tutte embedding

• Vertex separator

Notes

References