graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a connected

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties * Graph (topology), a topological space resembling a graph in the sense of discr ...

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 In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...

) has connectivity ''k'' if ''k'' is the size of the smallest subset of vertices such that the graph becomes disconnected if you delete them. Complete graphs are not included in this version of the definition since they cannot be disconnected by deleting vertices. The complete graph with ''n'' vertices has connectivity ''n'' − 1, as implied by the first definition. 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 In the mathematical discipline of graph theory, Menger's theorem says that in a finite graph, the size of a minimum cut set is equal to the maximum number of disjoint paths that can be found between any pair of vertices. Proved by Karl Menger i ...

. This definition produces the same answer, ''n'' − 1, for the connectivity of the complete graph ''K''_''n''. A 1-connected graph is called connected; a 2-connected graph is called biconnected. A 3-connected graph is called triconnected.

Applications

Polyhedral combinatorics

The 1-

skeleton A skeleton is the structural frame that supports the body of an animal. There are several types of skeletons, including the exoskeleton, which is the stable outer shell of an organism, the endoskeleton, which forms the support structure inside ...

of any ''k''-dimensional convex

polytope In elementary geometry, a polytope is a geometric object with flat sides ('' faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an ...

forms a ''k''-vertex-connected graph (

Balinski's theorem In polyhedral combinatorics, a branch of mathematics, Balinski's theorem is a statement about the graph-theoretic structure of three-dimensional convex polyhedra and higher-dimensional convex polytopes. It states that, if one forms an undirected ...

, ). As a partial converse,

Steinitz's theorem In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graph ...

states that any 3-vertex-connected

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...

forms the skeleton of a convex

polyhedron In geometry, a polyhedron (plural polyhedra or polyhedrons; ) is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices. A convex polyhedron is the convex hull of finitely many points, not all on ...

Computational complexity

The vertex-connectivity of an input graph ''G'' can be computed in polynomial time in the following way''The algorithm design manual'', p 506, and ''Computational discrete mathematics: combinatorics and graph theory with Mathematica'', p. 290-291 consider all possible pairs

(s, t)

of nonadjacent nodes to disconnect, using

to justify that the minimal-size separator for

(s, t)

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 optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate. The maximum flow problem can be seen as a special case of more complex network flow problems, such ...

in the graph between

s

and

t

with capacity 1 to each edge, noting that a flow of

k

in this graph corresponds, by the

integral flow theorem In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate. The maximum flow problem can be seen as a special case of more complex network flow problems, such ...

, to

k

pairwise edge-independent paths from

s

t

Notes

References