Inmathematics andcomputer science,connectivity is one of the basic concepts ofgraph theory: it asks for theminimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or moreisolated subgraphs.^[1] It is closely related to the theory ofnetwork flow problems. The connectivity of a graph is an important measure of its resilience as a network.

In anundirected graphG, twoverticesu andv are calledconnected ifG contains apath fromu tov. Otherwise, they are calleddisconnected. If the two vertices are additionally connected by a path of length1 (that is, they are the endpoints of a single edge), the vertices are calledadjacent.

Agraph is said to beconnected if every pair of vertices in the graph is connected. This means that there is apath between every pair of vertices. An undirected graph that is not connected is calleddisconnected. An undirected graphG is therefore disconnected if there exist two vertices inG such that no path inG has these vertices as endpoints. A graph with just one vertex is connected. Anedgeless graph with two or more vertices is disconnected.

Adirected graph is calledweakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph. It isunilaterally connected or unilateral (also calledsemiconnected) if it contains a directed path fromu tov or a directed path fromv tou for every pair of verticesu,v.^[2] It isstrongly connected, or simply strong, if it contains a directed path fromu tov and a directed path fromv tou for every pair of verticesu,v.

Aconnected component is a maximal connected subgraph of an undirected graph. Each vertex belongs to exactly one connected component, as does each edge. A graph is connectedif and only if it has exactly one connected component.

Thestrong components are the maximal strongly connected subgraphs of a directed graph.

Avertex cut orseparating set of a connected graphG is a set of vertices whose removal rendersG disconnected. Thevertex connectivityκ(G) (whereG is not acomplete graph) is the size of a smallest vertex cut. A graph is calledk-vertex-connected ork-connected if its vertex connectivity isk or greater.

More precisely, any graphG (complete or not) is said to bek-vertex-connected if it contains at leastk + 1 vertices, but does not contain a set ofk − 1 vertices whose removal disconnects the graph; andκ(G) is defined as the largestk such thatG isk-connected. In particular, acomplete graph withn vertices, denotedK_n, has no vertex cuts at all, butκ(K_n) =n − 1.

Avertex cut for two verticesu andv is a set of vertices whose removal from the graph disconnectsu andv. Thelocal connectivityκ(u,v) is the size of a smallest vertex cut separatingu andv. Local connectivity is symmetric for undirected graphs; that is,κ(u,v) =κ(v,u). Moreover, except for complete graphs,κ(G) equals the minimum ofκ(u,v) over all nonadjacent pairs of verticesu,v.

2-connectivity is also calledbiconnectivity and3-connectivity is also calledtriconnectivity. A graphG which is connected but not2-connected is sometimes calledseparable.

Analogous concepts can be defined for edges. In the simple case in which cutting a single, specific edge would disconnect the graph, that edge is called abridge. More generally, an edge cut ofG is a set of edges whose removal renders the graph disconnected. Theedge-connectivityλ(G) is the size of a smallest edge cut, and the local edge-connectivityλ(u,v) of two verticesu,v is the size of a smallest edge cut disconnectingu fromv. Again, local edge-connectivity is symmetric. A graph is calledk-edge-connected if its edge connectivity isk or greater.

A graph is said to bemaximally connected if its connectivity equals its minimumdegree. A graph is said to bemaximally edge-connected if its edge-connectivity equals its minimum degree.^[3]

A graph is said to besuper-connected orsuper-κ if every minimum vertex cut isolates a vertex. A graph is said to behyper-connected orhyper-κ if the deletion of each minimum vertex cut creates exactly two components, one of which is an isolated vertex. A graph issemi-hyper-connected orsemi-hyper-κ if any minimum vertex cut separates the graph into exactly two components.^[4]

More precisely: aG connected graph is said to besuper-connected orsuper-κ if all minimum vertex-cuts consist of the vertices adjacent with one (minimum-degree) vertex.AG connected graph is said to besuper-edge-connected orsuper-λ if all minimum edge-cuts consist of the edges incident on some (minimum-degree) vertex.^[5]

A cutsetX ofG is called a non-trivial cutset ifX does not contain the neighborhoodN(u) of any vertexu ∉X. Then thesuperconnectivity${\displaystyle {\kappa }_1}$ ofG is$${\displaystyle {\kappa }_1(G)=min\{|X|:X\text{ is a non-trivial cutset}\}.}$$

A non-trivial edge-cut and theedge-superconnectivity${\displaystyle {\lambda }_1(G)}$ are defined analogously.^[6]

One of the most important facts about connectivity in graphs isMenger's theorem, which characterizes the connectivity and edge-connectivity of a graph in terms of the number of independent paths between vertices.

Ifu andv are vertices of a graphG, then a collection of paths betweenu andv is called independent if no two of them share a vertex (other thanu andv themselves). Similarly, the collection is edge-independent if no two paths in it share an edge. The number of mutually independent paths betweenu andv is written asκ′(u,v), and the number of mutually edge-independent paths betweenu andv is written asλ′(u,v).

Menger's theorem asserts that for distinct verticesu,v,λ(u,v) equalsλ′(u,v), and ifu is also not adjacent tov thenκ(u,v) equalsκ′(u,v).^[7][8] This fact is actually a special case of themax-flow min-cut theorem.

The problem of determining whether two vertices in a graph are connected can be solved efficiently using asearch algorithm, such asbreadth-first search. More generally, it is easy to determine computationally whether a graph is connected (for example, by using adisjoint-set data structure), or to count the number of connected components. A simple algorithm might be written inpseudo-code as follows:

1. Begin at any arbitrary node of the graphG.
2. Proceed from that node using either depth-first or breadth-first search, counting all nodes reached.
3. Once the graph has been entirely traversed, if the number of nodes counted is equal to the number of nodes ofG, the graph is connected; otherwise it is disconnected.

ByMenger's theorem, for any two verticesu andv in a connected graphG, the numbersκ(u,v) andλ(u,v) can be determined efficiently using themax-flow min-cut algorithm. The connectivity and edge-connectivity ofG can then be computed as the minimum values ofκ(u,v) andλ(u,v), respectively.

Incomputational complexity theory,SL is the class of problemslog-space reducible to the problem of determining whether two vertices in a graph are connected, which was proved to be equal toL byOmer Reingold in 2004.^[9] Hence, undirected graph connectivity may be solved inO(logn) space.

The problem of computing the probability that aBernoulli random graph is connected is called network reliability and the problem of computing whether two given vertices are connected the ST-reliability problem. Both of these are#P-hard.^[10]

The number of distinct connected labeled graphs withn nodes is tabulated in theOn-Line Encyclopedia of Integer Sequences as sequenceA001187. The first few non-trivial terms are

• The vertex- and edge-connectivities of a disconnected graph are both0.
• 1-connectedness is equivalent to connectedness for graphs of at least two vertices.
• Thecomplete graph onn vertices has edge-connectivity equal ton − 1. Every othersimple graph onn vertices has strictly smaller edge-connectivity.
• In atree, the local edge-connectivity between any two distinct vertices is1.

• The vertex-connectivity of a graph is less than or equal to its edge-connectivity. That is,κ(G) ≤λ(G).
• The edge-connectivity for a graph with at least 2 vertices is less than or equal to the minimumdegree of the graph because removing all the edges that are incident to a vertex of minimum degree will disconnect that vertex from the rest of the graph.^[1]
• For avertex-transitive graph of degreed, we have:2(d + 1)/3 ≤κ(G) ≤λ(G) =d.^[11]
• For a vertex-transitive graph of degreed ≤ 4, or for any (undirected) minimalCayley graph of degreed, or for anysymmetric graph of degreed, both kinds of connectivity are equal:κ(G) =λ(G) =d.^[12]

• Connectedness is preserved bygraph homomorphisms.
• IfG is connected then itsline graphL(G) is also connected.
• A graphG is2-edge-connected if and only if it has an orientation that is strongly connected.
• Balinski's theorem states that thepolytopal graph (1-skeleton) of ak-dimensionalconvex polytope is ak-vertex-connected graph.^[13]Steinitz's previous theorem that any 3-vertex-connectedplanar graph is a polytopal graph (Steinitz's theorem) gives a partialconverse.
• According to a theorem ofG. A. Dirac, if a graph isk-connected fork ≥ 2, then for every set ofk vertices in the graph there is acycle that passes through all the vertices in the set.^[14][15] The converse is true whenk = 2.

• Algebraic connectivity
• Cheeger constant (graph theory)
• Dynamic connectivity,Disjoint-set data structure
• Expander graph
• Strength of a graph

• Graph connectivity

• Articles with short description
• Short description is different from Wikidata