Vertex connectivity

Quality 0.50 · 3 views · Updated 2 months ago

Graph which remains connected when k or fewer nodes removed

title: "Vertex connectivity" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["graph-connectivity", "graph-families"] description: "Graph which remains connected when k or fewer nodes removed" topic_path: "general/graph-connectivity" source: "https://en.wikipedia.org/wiki/Vertex_connectivity" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Graph which remains connected when k or fewer nodes removed ::

::figure[src="https://upload.wikimedia.org/wikipedia/commons/b/b3/4-connected_graph.svg" caption="A graph with connectivity 4 and not 5: The graph remains connected whichever 3 vertices are removed but removing all but 2 opposing vertices (i.e. removing 4) leaves a disconnected graph."] ::

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

The vertex-connectivity, or just connectivity, of a graph is the largest k for which the graph is k-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, there is no subset whose removal would disconnect the graph. Some sources modify the definition of connectivity to handle this case, by defining it as the size of the smallest subset of vertices whose deletion results in either a disconnected graph or a single vertex. For this variation, the connectivity of a complete graph K_n is n-1.

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, n − 1, for the connectivity of the complete graph K**n.

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).{{citation | last = Balinski | first = M. L. | authorlink = Michel Balinski | issue = 2 | journal = Pacific Journal of Mathematics | pages = 431–434 | title = On the graph structure of convex polyhedra in n-space | volume = 11 | year = 1961 | doi = 10.2140/pjm.1961.11.431 | doi-access = free

Computational complexity

The vertex-connectivity of an input graph G can be computed in polynomial time in the following way consider all possible pairs (s, t) of nonadjacent nodes to disconnect, using Menger's theorem 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 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, to k pairwise edge-independent paths from s to t.

Properties

Let k≥2.

  • Every k-connected graph of order at least 2k contains a cycle of length at least 2k
  • In a k-connected graph, any k vertices in G lie on a common cycle.

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

''k''-linked graph

A graph with at least 2k vertices is called k-linked if there are k disjoint paths for any sequences a_1,\dots,a_k and b_1,\dots, b_k of 2k distinct vertices. Every k-linked graph is (2k-1)-connected graph, but not necessarily 2k-connected.

If a graph is 2k-connected and has average degree of at least 16k, then it is k-linked.

Notes

References

  • {{citation | last = Diestel | first = Reinhard | author-link = Reinhard Diestel | edition = 3rd | isbn = 978-3-540-26183-4 | location = Berlin, New York | publisher = Springer-Verlag | title = Graph Theory | url = http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ | year = 2005}}
  • {{citation | last = Diestel | first = Reinhard | edition = corrected 4th electronic | title = Graph Theory | year = 2012}}
  • {{citation | last = Diestel | first = Reinhard | edition = 5th | isbn = 978-3-662-53621-6 | location = Berlin, New York | publisher = Springer-Verlag | title = Graph Theory | url = https://diestel-graph-theory.com/index.html | year = 2016}}

References

  1. Schrijver. (12 February 2003). "Combinatorial Optimization". Springer.
  2. (2021). "Line Graphs and Line Digraphs". Springer Nature.
  3. ''The algorithm design manual'', p 506, and ''Computational discrete mathematics: combinatorics and graph theory with Mathematica'', p. 290-291
  4. {{harvtxt. Diestel. 2016, p.84
  5. {{harvtxt. Diestel. 2012, p.65.
  6. {{harvtxt. Diestel. 2016, p.85
  7. {{harvtxt. Diestel. 2016, p.75

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::

graph-connectivitygraph-families