Hubbry Logo
Connectivity (graph theory)Connectivity (graph theory)Main
Open search
Connectivity (graph theory)
Community hub
Connectivity (graph theory)
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Connectivity (graph theory)
Connectivity (graph theory)
Connectivity (graph theory)
View on Wikipedia
from Wikipedia
This graph becomes disconnected when the right-most node in the gray area on the left is removed
This graph becomes disconnected when the dashed edge is removed.

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgraphs.[1] It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network.

Connected vertices and graphs

[edit]
With vertex 0, this graph is disconnected. The rest of the graph is connected.

In an undirected graph G, two vertices u and v are called connected if G contains a path from u to v. Otherwise, they are called disconnected. If the two vertices are additionally connected by a path of length 1 (that is, they are the endpoints of a single edge), the vertices are called adjacent.

A graph is said to be connected if every pair of vertices in the graph is connected. This means that there is a path between every pair of vertices. An undirected graph that is not connected is called disconnected. An undirected graph G is therefore disconnected if there exist two vertices in G such that no path in G has these vertices as endpoints. A graph with just one vertex is connected. An edgeless graph with two or more vertices is disconnected.

A directed graph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph. It is unilaterally connected or unilateral (also called semiconnected) if it contains a directed path from u to v or a directed path from v to u for every pair of vertices u, v.[2] It is strongly connected, or simply strong, if it contains a directed path from u to v and a directed path from v to u for every pair of vertices u, v.

Components and cuts

[edit]

A connected 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 connected if and only if it has exactly one connected component.

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

A vertex cut or separating set of a connected graph G is a set of vertices whose removal renders G disconnected. The vertex connectivity κ(G) (where G is not a complete graph) is the size of a smallest vertex cut. A graph is called k-vertex-connected or k-connected if its vertex connectivity is k or greater.

More precisely, any graph G (complete or not) is said to be k-vertex-connected if it contains at least k + 1 vertices, but does not contain a set of k − 1 vertices whose removal disconnects the graph; and κ(G) is defined as the largest k such that G is k-connected. In particular, a complete graph with n vertices, denoted Kn, has no vertex cuts at all, but κ(Kn) = n − 1.

A vertex cut for two vertices u and v is a set of vertices whose removal from the graph disconnects u and v. The local connectivity κ(u, v) is the size of a smallest vertex cut separating u and v. 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 vertices u, v.

2-connectivity is also called biconnectivity and 3-connectivity is also called triconnectivity. A graph G which is connected but not 2-connected is sometimes called separable.

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 a bridge. More generally, an edge cut of G is a set of edges whose removal renders the graph disconnected. The edge-connectivity λ(G) is the size of a smallest edge cut, and the local edge-connectivity λ(u, v) of two vertices u, v is the size of a smallest edge cut disconnecting u from v. Again, local edge-connectivity is symmetric. A graph is called k-edge-connected if its edge connectivity is k or greater.

A graph is said to be maximally connected if its connectivity equals its minimum degree. A graph is said to be maximally edge-connected if its edge-connectivity equals its minimum degree.[3]

Super- and hyper-connectivity

[edit]

A graph is said to be super-connected or super-κ if every minimum vertex cut isolates a vertex. A graph is said to be hyper-connected or hyper-κ if the deletion of each minimum vertex cut creates exactly two components, one of which is an isolated vertex. A graph is semi-hyper-connected or semi-hyper-κ if any minimum vertex cut separates the graph into exactly two components.[4]

More precisely: a G connected graph is said to be super-connected or super-κ if all minimum vertex-cuts consist of the vertices adjacent with one (minimum-degree) vertex. A G connected graph is said to be super-edge-connected or super-λ if all minimum edge-cuts consist of the edges incident on some (minimum-degree) vertex.[5]

A cutset X of G is called a non-trivial cutset if X does not contain the neighborhood N(u) of any vertex u ∉ X. Then the superconnectivity of G is

A non-trivial edge-cut and the edge-superconnectivity are defined analogously.[6]

Menger's theorem

[edit]
Main article: Menger's theorem

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

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

Menger's theorem asserts that for distinct vertices u,v, λ(u, v) equals λ′(u, v), and if u is also not adjacent to v then κ(u, v) equals κ′(u, v).[7][8] This fact is actually a special case of the max-flow min-cut theorem.

Computational aspects

[edit]

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

  1. Begin at any arbitrary node of the graph G.
  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 of G, the graph is connected; otherwise it is disconnected.

By Menger's theorem, for any two vertices u and v in a connected graph G, the numbers κ(u, v) and λ(u, v) can be determined efficiently using the max-flow min-cut algorithm. The connectivity and edge-connectivity of G can then be computed as the minimum values of κ(u, v) and λ(u, v), respectively.

In computational complexity theory, SL is the class of problems log-space reducible to the problem of determining whether two vertices in a graph are connected, which was proved to be equal to L by Omer Reingold in 2004.[9] Hence, undirected graph connectivity may be solved in O(log n) space.

The problem of computing the probability that a Bernoulli 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]

Number of connected graphs

[edit]
Main article: Graph enumeration

The number of distinct connected labeled graphs with n nodes is tabulated in the On-Line Encyclopedia of Integer Sequences as sequence A001187. The first few non-trivial terms are

The number and images of connected graphs with 4 nodes
n graphs
1 1
2 1
3 4
4 38
5 728
6 26704
7 1866256
8 251548592

Examples

[edit]
  • The vertex- and edge-connectivities of a disconnected graph are both 0.
  • 1-connectedness is equivalent to connectedness for graphs of at least two vertices.
  • The complete graph on n vertices has edge-connectivity equal to n − 1. Every other simple graph on n vertices has strictly smaller edge-connectivity.
  • In a tree, the local edge-connectivity between any two distinct vertices is 1.

Bounds on connectivity

[edit]
  • 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 minimum degree 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 a vertex-transitive graph of degree d, we have: 2(d + 1)/3 ≤ κ(G) ≤ λ(G) = d.[11]
  • For a vertex-transitive graph of degree d ≤ 4, or for any (undirected) minimal Cayley graph of degree d, or for any symmetric graph of degree d, both kinds of connectivity are equal: κ(G) = λ(G) = d.[12]

Other properties

[edit]

See also

[edit]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Connectivity (graph theory)

View on Grokipedia
from Grokipedia
In graph theory, connectivity refers to the extent to which the vertices of a graph are interlinked, with a basic connected graph defined as one in which there exists at least one path between every pair of vertices. More advanced measures quantify this resilience: vertex-connectivity (κ(G)) is the smallest number of vertices whose removal disconnects the graph or reduces it to a single vertex, while edge-connectivity (λ(G)) is the smallest number of edges whose removal achieves the same effect. These concepts, formalized in the early 20th century, underpin the study of network robustness and are central to theorems like Menger's theorem, which equates the maximum number of vertex-disjoint paths between two non-adjacent vertices to the minimum size of a vertex separator disconnecting them. The foundational work on connectivity was introduced by Hassler Whitney in 1932, who defined k-connectivity as the property where at least k vertices must be removed to disconnect the graph, and established key inequalities relating vertex-connectivity, edge-connectivity, and the minimum degree δ(G) of the graph: κ(G) ≤ λ(G) ≤ δ(G). (1927), predating Whitney, provides a path-based characterization that generalizes to both vertex and edge versions, stating that for any two non-adjacent vertices, the maximum number of internally vertex-disjoint paths equals the minimum vertex cut size separating them. A graph is k-vertex-connected if it has at least k+1 vertices and remains connected after removing any k-1 vertices, equivalently if every pair of vertices is joined by k internally vertex-disjoint paths. Connectivity plays a pivotal role in applications ranging from network design and fault-tolerant systems to , where highly connected graphs ensure redundancy against failures. For instance, complete graphs K_n exhibit maximum connectivity of n-1, while trees have connectivity 1, highlighting the from minimally to maximally robust structures. Further results, such as those on 2-connected graphs (built from cycles via ear decompositions) and 3-connected graphs (starting from K_4 with specific additions), extend these ideas to structural characterizations.

Basic Concepts

Connected Graphs

In graph theory, two vertices in an undirected graph are connected if there exists a path between them, where a path is a sequence of distinct vertices linked by edges. A graph is connected if every pair of its vertices is connected by such a path; otherwise, it is disconnected. The trivial graph consisting of a single vertex is considered connected by convention, as there are no pairs of distinct vertices to connect. The , consisting of no vertices (and no edges), is generally not considered connected, as connectivity is typically defined for non-empty graphs. For example, the path graph PnP_n, which consists of nn vertices connected in a linear sequence by n−1n-1 edges, is connected for any n≥1n \geq 1. A simple disconnected graph might consist of two isolated vertices with no edges between them, where no path exists linking the pair. The term "connected" in this context was formalized in early 20th-century graph theory. In directed graphs, connectivity variants account for edge orientations. A directed graph is weakly connected if its underlying undirected graph—obtained by ignoring directions—is connected. It is unilaterally connected if, for every pair of distinct vertices, there is a directed path from one to the other in at least one direction. Strongest is strong connectivity, where there exists a directed path between every pair of vertices in both directions.

Connected Components

In graph theory, a connected component of a graph GG is a maximal connected subgraph, meaning it is connected and no additional vertices or edges from GG can be added while preserving connectivity. This subgraph induces a partition of the vertex set V(G)V(G), where each component consists of all vertices reachable from one another via paths in GG. Isolated vertices, which have no incident edges, each form a singleton connected component. The relation of being in the same connected component defines an equivalence relation on the vertices of GG: it is reflexive (every vertex reaches itself via a trivial path), symmetric (paths are bidirectional in undirected graphs), and transitive (concatenating paths preserves reachability). The equivalence classes under this relation precisely correspond to the connected components, partitioning V(G)V(G) into disjoint sets where intra-component connectivity holds but inter-component paths do not. The number of such components is denoted by c(G)c(G), and GG is connected if and only if c(G)=1c(G) = 1. Connected components in undirected graphs can be identified algorithmically using (DFS) or (BFS), starting from each unvisited vertex and marking all reachable vertices as part of the current component; this process repeats until all vertices are visited, yielding all components in linear time relative to the number of vertices and edges. For directed graphs, connectivity notions extend to weakly connected components and . A weakly connected component is a maximal subdigraph where, ignoring edge directions, every pair of distinct vertices is connected by an undirected path; these are essentially the connected components of the underlying undirected graph. In contrast, a is a maximal subdigraph where, for every pair of distinct vertices uu and vv, there is a directed path from uu to vv and from vv to uu. These strong components partition the vertices, with the condensation graph (where each strong component is contracted to a single vertex) forming a .

Measures of Connectivity

Vertex Connectivity

In graph theory, the vertex connectivity of a graph GG, denoted κ(G)\kappa(G), is defined as the size of the smallest vertex cut, where a vertex cut is a set of vertices whose removal from GG either disconnects the graph or reduces it to a single vertex (assuming ∣V(G)∣≥2|V(G)| \geq 2). This measure quantifies the robustness of GG against vertex failures, as removing fewer than κ(G)\kappa(G) vertices leaves GG connected. If GG is disconnected, then κ(G)=0\kappa(G) = 0. For the complete graph KnK_n with n≥2n \geq 2 vertices, κ(Kn)=n−1\kappa(K_n) = n-1, since the removal of n−1n-1 vertices isolates the remaining one. The local vertex connectivity between two distinct vertices uu and vv in GG, denoted κ(u,v)\kappa(u,v), is the size of the smallest set of vertices whose removal separates uu from vv (i.e., no path remains between them). For non-adjacent uu and vv, κ(u,v)\kappa(u,v) equals the maximum number of internally vertex-disjoint paths from uu to vv. In a non-complete connected graph GG, the vertex connectivity is given by κ(G)=min⁡{κ(u,v)∣u,v∈V(G),u≠v,uv∉E(G)}\kappa(G) = \min\{\kappa(u,v) \mid u,v \in V(G), u \neq v, uv \notin E(G)\}. A connected graph GG has κ(G)=1\kappa(G) = 1 if and only if it contains an articulation point (also called a cut vertex), whose removal increases the number of connected components. It holds that κ(G)≤δ(G)\kappa(G) \leq \delta(G), where δ(G)\delta(G) is the minimum degree of GG, because the neighbors of a minimum-degree vertex form a vertex cut separating that vertex from the rest of the graph. Additionally, Whitney's inequality states that κ(G)≤λ(G)\kappa(G) \leq \lambda(G), where λ(G)\lambda(G) is the edge connectivity of GG, highlighting vertex connectivity as a stricter bound compared to its edge-based counterpart.

Edge Connectivity

In , the edge connectivity of a connected graph GG, denoted λ(G)\lambda(G), is defined as the minimum number of edges whose removal disconnects GG. This measure quantifies the graph's resilience to edge failures, with λ(G)=0\lambda(G) = 0 for any disconnected graph. The local edge connectivity between two distinct vertices uu and vv in GG, denoted λ(u,v)\lambda(u,v), is the size of the smallest set of edges whose removal separates uu from vv, or equivalently, the maximum number of edge-disjoint paths from uu to vv. The global edge connectivity satisfies λ(G)=min⁡u,v∈V(G),u≠vλ(u,v)\lambda(G) = \min_{u,v \in V(G), u \neq v} \lambda(u,v). Special cases highlight key structural properties: λ(G)=1\lambda(G) = 1 if GG contains a bridge, an edge whose removal disconnects the graph; for the KnK_n with n≥2n \geq 2, λ(Kn)=n−1\lambda(K_n) = n-1. Bridges are precisely the edges that do not lie on any cycle in GG, as their removal breaks the unique path between the components they connect. A fundamental bound relates edge connectivity to the minimum degree δ(G)\delta(G): λ(G)≤δ(G)\lambda(G) \leq \delta(G), since removing all edges incident to a minimum-degree vertex disconnects it from the rest of the graph. Whitney's inequality strengthens this by positioning edge connectivity between vertex connectivity κ(G)\kappa(G) and minimum degree: κ(G)≤λ(G)≤δ(G)\kappa(G) \leq \lambda(G) \leq \delta(G) for any graph GG with at least two vertices.

Key Theorems and Characterizations

Menger's Theorem

Menger's theorem provides a fundamental characterization of connectivity in graphs by relating the minimum size of separators to the maximum number of disjoint paths between vertices. In its vertex version, for non-adjacent vertices ss and tt in an undirected graph GG, the minimum number of vertices whose removal disconnects ss from tt—known as the size of a minimum ss-tt vertex separator—equals the maximum number of internally vertex-disjoint ss-tt paths in GG. This equivalence, denoted as κ(s,t)=ν(s,t)\kappa(s,t) = \nu(s,t), where κ(s,t)\kappa(s,t) is the separator size and ν(s,t)\nu(s,t) is the path number, captures the local vertex connectivity between specific pairs. The edge version of the states that, for any two vertices uu and vv in GG, the minimum number of edges whose removal disconnects uu from vv—the size of a minimum uu-vv edge separator—equals the maximum number of edge-disjoint uu-vv paths in GG. Denoted λ(u,v)=μ(u,v)\lambda(u,v) = \mu(u,v), where λ(u,v)\lambda(u,v) is the edge separator size and μ(u,v)\mu(u,v) is the edge-disjoint path number, this version directly parallels the vertex case but focuses on edges rather than internal vertices. These local characterizations extend to global connectivity measures: for a connected graph GG, the vertex connectivity κ(G)\kappa(G) equals the minimum of κ(u,v)\kappa(u,v) over all non-adjacent pairs u,v∈V(G)u,v \in V(G), implying GG is kk-connected if and only if every pair of vertices admits kk internally disjoint paths. Similarly, the edge connectivity λ(G)\lambda(G) is the minimum of λ(u,v)\lambda(u,v) over all pairs u,vu,v, so GG is kk-edge-connected if and only if every pair admits kk edge-disjoint paths. Proved by in , the theorem laid foundational groundwork for later developments in network flow theory, where the weighted generalizes it. Proofs typically proceed by induction on the number of vertices or via the construction of augmenting paths that alternately use existing paths and separators to build disjoint ones until no further augmentation is possible. The theorem extends naturally to directed graphs, where the vertex (or edge) version equates the minimum size of a separator to the maximum number of internally vertex-disjoint (or edge-disjoint) directed paths from a source set to a sink set, preserving the core duality.

Bounds on Connectivity

Whitney's inequality provides fundamental upper bounds on the connectivity parameters of a simple graph GG. Specifically, the vertex connectivity κ(G)\kappa(G) satisfies κ(G)≤λ(G)≤δ(G)\kappa(G) \leq \lambda(G) \leq \delta(G), where λ(G)\lambda(G) denotes the edge connectivity and δ(G)\delta(G) the minimum degree. The second part, λ(G)≤δ(G)\lambda(G) \leq \delta(G), follows from the observation that removing all edges incident to a vertex of minimum degree disconnects that vertex from the rest of the graph, yielding an edge cut of size at most δ(G)\delta(G). The first part, κ(G)≤λ(G)\kappa(G) \leq \lambda(G), arises from the fact that any minimum vertex cut corresponds to a vertex cut whose removal induces an edge cut of no greater size, leveraging minimality arguments from path decompositions. An immediate upper bound on vertex connectivity is κ(G)≤n−1\kappa(G) \leq n-1, where n=∣V(G)∣n = |V(G)|, with equality holding if and only if GG is the KnK_n. This follows directly from the definition, as removing n−1n-1 vertices leaves a single isolated vertex, disconnecting the graph, and in KnK_n, fewer than n−1n-1 vertices cannot separate any pair. For vertex-transitive graphs, which are necessarily regular of degree δ(G)\delta(G), tighter bounds apply: ⌈2(δ(G)+1)/3⌉≤κ(G)≤δ(G)\lceil 2(\delta(G) + 1)/3 \rceil \leq \kappa(G) \leq \delta(G). The upper bound is trivial from Whitney's inequality, while the lower bound uses and expansion properties to ensure sufficiently many vertex-disjoint paths between any pair, preventing small cuts. Mader's theorem states that every graph with average degree at least 4κ4\kappa contains a subgraph of vertex connectivity at least κ\kappa (for example, for κ=2\kappa=2, average degree at least 8 guarantees a 2-connected subgraph). Proofs rely on iteratively contracting high-degree components and applying Dirac-type degree conditions to build connected structures without small cuts. In random graphs, asymptotic bounds reveal sharp thresholds for connectivity. For the G(n,p)G(n,p), the probability that the graph is connected transitions from near 0 to near 1 around p=(ln⁡n)/np = (\ln n)/n; more precisely, if p=(ln⁡n+c)/np = (\ln n + c)/n for constant cc, then P(G(n,p) is connected)→e−e−c\mathbb{P}(G(n,p) \text{ is connected}) \to e^{-e^{-c}} as n→∞n \to \infty. Above this threshold, the minimum degree is at least 1 with high probability, implying κ(G)≥1\kappa(G) \geq 1, and higher connectivity follows from the resulting high minimum degree. These thresholds are derived using the expected number of isolated vertices and union bounds on small components.

Advanced Connectivity Notions

k-Connected Graphs

A graph GG is said to be kk-vertex-connected if it has more than kk vertices and remains connected whenever fewer than kk vertices are removed. Similarly, GG is kk-edge-connected if it remains connected after the removal of fewer than kk edges. The vertex connectivity κ(G)\kappa(G) is the largest integer kk such that GG is kk-vertex-connected, and likewise for edge connectivity λ(G)\lambda(G). For k=1k = 1, a graph is 1-vertex-connected if and only if it is connected. For k=2k = 2, a 2-vertex-connected graph is termed biconnected and contains no articulation points (also called cut vertices), which are vertices whose removal increases the number of connected components. A 2-edge-connected graph has no bridges, which are edges whose removal disconnects the graph. Articulation points can be detected efficiently using a (DFS) traversal that tracks discovery times and low values for each vertex, as developed in the seminal by Hopcroft and Tarjan. This method identifies articulation points in linear time relative to the number of vertices and edges by checking conditions such as a vertex having multiple children in the DFS or a non-root vertex with no back edge to an ancestor. The biconnected components of a graph, also known as blocks, are the maximal subgraphs that are 2-vertex-connected. These components can be found using the same DFS-based approach, where edges are stacked during traversal and popped to form components upon encountering articulation points or completing subtrees. Biconnected components partition the edges of the graph, sharing only articulation points between them, and provide a block-cut that captures the overall connectivity. One construction of minimal kk-connected graphs on nn vertices is the Harary graph Hk,nH_{k,n}, which achieves the smallest possible number of edges while ensuring kk-connectivity. For even k=2pk = 2p, the graph is formed by arranging nn vertices in a cycle and connecting each vertex to its pp nearest neighbors in both clockwise and counterclockwise directions. For odd k=2p+1k = 2p + 1, each vertex connects to its pp nearest neighbors in each direction, plus a connection to the diametrically opposite vertex (adjusted for even or odd nn). These graphs are kk-regular when possible and serve as extremal examples for connectivity bounds. Sufficient conditions for kk-connectivity often involve degree constraints.

Super- and Hyper-Connectivity

In , super- and hyper-connectivity extend the notion of k-connectivity by imposing structural conditions on the minimum cuts of a graph, ensuring that disconnections occur in a highly specific manner. These concepts are particularly relevant for analyzing fault-tolerant structures where basic connectivity thresholds are insufficient to guarantee desirable separation properties. A graph GG is super-vertex-connected if every minimum vertex cut isolates a vertex, meaning the removal of such a cut leaves at least one isolated vertex in the remaining graph. A graph is hyper-vertex-connected if every minimum vertex cut creates exactly two components, one of which is an isolated vertex. A related variant is semi-hyper-connected, where every minimum vertex cut separates the graph into exactly two components, without requiring isolation of a single vertex. Note that hyper-vertex-connected graphs are both super-vertex-connected and semi-hyper-connected. For edges, a graph is super-edge-connected if every minimum edge cut consists of all edges incident to a single vertex, effectively isolating that vertex via its full neighborhood edges. The superconnectivity parameter κ1(G)\kappa_1(G) for a connected graph GG is defined as the size of the smallest non-trivial vertex cut that does not isolate any single vertex, i.e., a cut whose removal disconnects GG into at least two components each of size at least 2; if no such cut exists, κ1(G)=∞\kappa_1(G) = \infty. Graphs exhibiting super- or hyper-vertex-connectivity often imply high regularity, as the vertex connectivity κ(G)\kappa(G) equals the minimum degree δ(G)\delta(G), since minimum cuts align precisely with the neighborhoods of minimum-degree vertices. For instance, complete graphs KnK_n (for n≥2n \geq 2) are super-vertex-connected, with minimum cuts of size n−1n-1 isolating any chosen vertex, while cycles CnC_n (for n≥3n \geq 3) are super-edge-connected, as their minimum edge cuts of size 2 consist of the two incident edges to any vertex. These notions were introduced in the early to enhance the analysis of fault-tolerant networks, with foundational work by Fiol, Fàbrega, and Escudero establishing the framework for superconnectivity in graphs and digraphs.

Computational Aspects

Algorithms for Computing Connectivity

Determining whether an undirected graph is connected can be achieved using (DFS) or (BFS), both of which run in O(∣V∣+∣E∣)O(|V| + |E|) time, where ∣V∣|V| is the number of vertices and ∣E∣|E| is the number of edges. These algorithms traverse the graph starting from an arbitrary vertex and check if all vertices are visited, thereby verifying overall connectivity. For the local vertex connectivity κ(u,v)\kappa(u,v) between two non-adjacent vertices uu and vv, or edge connectivity λ(u,v)\lambda(u,v), the problem reduces to finding the maximum flow in a derived , as justified by . Specifically, for κ(u,v)\kappa(u,v), construct a network where each vertex is split into an in-vertex and out-vertex connected by a unit-capacity edge, and original edges have infinite capacity; the max-flow value from uu to vv equals κ(u,v)\kappa(u,v). For λ(u,v)\lambda(u,v), assign unit capacities to edges directly. The Ford-Fulkerson method or its implementation via Edmonds-Karp using BFS finds this flow in O(∣V∣∣E∣2)O(|V| |E|^2) time. Recent almost-linear time maximum flow algorithms, such as those achieving O~(m)\tilde{O}(m) time where m=∣E∣m = |E|, enable faster computations for connectivity in practice. Computing the global vertex connectivity κ(G)\kappa(G) or edge connectivity λ(G)\lambda(G) of a graph GG requires finding the minimum over all pairs of non-adjacent vertices, which naively involves O(∣V∣2)O(|V|^2) max-flow computations and thus O(∣V∣3∣E∣2)O(|V|^3 |E|^2) time overall. More efficient approaches exist for specific cases; for instance, identifying articulation points (vertices whose removal increases the number of connected components) to bound κ(G)≤2\kappa(G) \leq 2 can be done using Tarjan's DFS-based algorithm in O(∣V∣+∣E∣)O(|V| + |E|) time. Specialized algorithms for higher connectivity, such as testing 3-edge-connectivity, achieve near-linear time by performing a single DFS traversal to find cut-pairs. In directed graphs, strong connectivity—where every pair of vertices has paths in both directions—can be tested by finding strongly connected components (SCCs). computes all SCCs in O(∣V∣+∣E∣)O(|V| + |E|) time using two DFS passes: one on the original graph to obtain finishing times, and one on the transpose graph in reverse finishing order. Alternatively, Tarjan's single-pass DFS algorithm identifies SCCs in the same linear time by tracking discovery times and low-link values to detect component roots. If the graph has exactly one SCC, it is strongly connected. Regarding computational complexity, the undirected s-t connectivity problem (deciding if there is a path between specified vertices s and t) is solvable in deterministic log-space (), as shown by Reingold's algorithm that simulates a via a zigzag product on expanders. Consequently, global undirected graph connectivity (testing if the graph is connected) is also in deterministic log-space, by fixing s and checking connectivity to all other vertices. In parallel models, connectivity can be computed efficiently on the PRAM; for example, a randomized EREW PRAM finds connected components in O(log⁡n)O(\log n) time using O(n+m/log⁡n)O(n + m / \log n) processors via techniques like pointer doubling on a BFS . For dynamic graphs supporting edge insertions and deletions with connectivity queries, as of 2025, structures achieve expected polylogarithmic worst-case update time and O(1)O(1) query time using randomized approaches based on hierarchical core graphs.

Enumeration of Connected Graphs

The enumeration of connected graphs is a central problem in , focusing on counting the distinct simple graphs that satisfy the connectivity condition, where every pair of vertices is linked by a path. This combinatorial task distinguishes between labeled graphs, where vertices are distinguishable, and unlabeled graphs, where only the structure matters up to . These counts provide insights into the density of connected structures within the space of all possible graphs and underpin asymptotic analyses and approaches. For labeled connected graphs on nn vertices, the sequence is given by OEIS A001187, which lists the numbers as 1 for n=1n=1, 1 for n=2n=2, 1 for n=3n=3, 4 for n=4n=4, 38 for n=5n=5, and 728 for n=6n=6. This sequence arises from recursive relations that subtract disconnected graphs from the total 2(n2)2^{\binom{n}{2}} labeled graphs. The following table summarizes the initial terms:
nnNumber of connected labeled graphs
11
21
31
44
538
6728
For unlabeled connected graphs on nn vertices, the sequence is OEIS A001349, with values 1 for n=1n=1, 1 for n=2n=2, 2 for n=3n=3, 6 for n=4n=4, 21 for n=5n=5, and 112 for n=6n=6. These counts account for graph isomorphisms using symmetry considerations, yielding fewer structures than the labeled case. Asymptotically, the number of labeled connected graphs on nn vertices is approximately 2(n2)2^{\binom{n}{2}}, as the proportion of connected graphs among all labeled graphs approaches 1 for large nn. More precise expansions, such as those for graphs with nn vertices and qq edges where q/n→x>1/2q/n \to x > 1/2, involve functions like wk−1(x)w_{k-1}(x) and α(x)\alpha(x) derived from singularity analysis. The exponential for labeled connected graphs, denoted C(x)=∑n≥1cnxnn!C(x) = \sum_{n \geq 1} c_n \frac{x^n}{n!} where cnc_n is the number of connected labeled graphs on nn vertices, satisfies log⁡(∑n≥02(n2)xnn!)=C(x)\log \left( \sum_{n \geq 0} 2^{\binom{n}{2}} \frac{x^n}{n!} \right) = C(x), reflecting the set-partition structure of disconnected graphs. Computational methods for enumeration include recursive algorithms that build graphs by adding vertices while ensuring connectivity, often implemented via systems for exact counts up to moderate nn. For unlabeled graphs, Pólya enumeration employs cycle indices of the to average fixed points under permutations, efficiently handling isomorphisms. Early asymptotic results trace to E. M. Wright's 1969 analysis, which provided foundational expansions for the number of connected graphs, building on prior exact enumerations.

Examples and Applications

Graph Families and Their Connectivity

In graph theory, the connectivity properties of standard graph families provide concrete illustrations of vertex and edge connectivity measures. The complete graph KnK_n on nn vertices, where every pair of distinct vertices is adjacent, exhibits the maximum possible connectivity for its order: its vertex connectivity κ(Kn)=n−1\kappa(K_n) = n-1 and edge connectivity λ(Kn)=n−1\lambda(K_n) = n-1. This follows from the fact that removing fewer than n−1n-1 vertices or edges leaves the graph connected, as the remaining structure retains a complete subgraph on the surviving vertices. Cycle graphs CnC_n for n≥3n \geq 3, consisting of nn vertices connected in a single closed loop, are minimally 2-connected among cycle-containing graphs: κ(Cn)=2\kappa(C_n) = 2 and λ(Cn)=2\lambda(C_n) = 2. Removing one vertex or edge from CnC_n yields a connected path graph, but removing two appropriately chosen vertices or adjacent edges disconnects it into two components. These families achieve the lower bound on connectivity given by the minimum degree δ(G)=2\delta(G) = 2. Trees, defined as connected acyclic graphs with at least two vertices, have the lowest positive connectivity among connected graphs: κ(T)=1\kappa(T) = 1 and λ(T)=1\lambda(T) = 1. Every non-trivial tree contains leaves (degree-1 vertices) or bridges (edges whose removal disconnects the graph), ensuring that a single vertex or edge removal disconnects it. The path graph PnP_n on n≥2n \geq 2 vertices, a special case of a tree forming a linear chain, similarly satisfies κ(Pn)=1\kappa(P_n) = 1 and λ(Pn)=1\lambda(P_n) = 1, as its endpoint vertices or connecting edges serve as cut vertices or bridges. The , a on 10 vertices known for its symmetry and non-planarity, achieves connectivity equal to its degree: κ(G)=3\kappa(G) = 3 and λ(G)=3\lambda(G) = 3. By , any two non-adjacent vertices in the Petersen graph are linked by three internally vertex-disjoint paths, confirming the vertex connectivity, while the edge connectivity matches due to the absence of bridges in this bridgeless . Hypercube graphs QdQ_d, which represent the dd-dimensional with 2d2^d vertices corresponding to binary strings of length dd and edges between strings differing in one bit, are dd-regular and dd-connected: κ(Qd)=d\kappa(Q_d) = d and λ(Qd)=d\lambda(Q_d) = d. This high connectivity arises from the graph's recursive , where QdQ_d consists of two copies of Qd−1Q_{d-1} linked by a , allowing dd vertex-disjoint or edge-disjoint paths between any pair of vertices. For disconnected graphs, such as the of two complete graphs Km∪KnK_m \cup K_n with m,n≥1m, n \geq 1, the vertex connectivity is κ(G)=0\kappa(G) = 0 by , as the graph lacks paths between vertices in different components. Similarly, the edge connectivity λ(G)=0\lambda(G) = 0, reflecting the absence of any connecting edges between components.

Applications in Network Resilience

In network design, graph connectivity measures such as vertex connectivity κ and edge connectivity λ are essential for ensuring fault-tolerant communication systems, where high values of κ and λ allow networks to withstand node or link failures without disrupting overall connectivity. For instance, the , modeled as an autonomous system (AS) graph, exhibits high edge connectivity to maintain resilience against failures, with studies showing that the AS-level remains connected even after removing a significant fraction of edges, supporting robust global . This fault-tolerance is critical for designing communication infrastructures that prioritize redundancy, as seen in protocols that leverage k-edge-connected subgraphs to route traffic reliably under adversarial or random failures. In very-large-scale integration (VLSI) circuits, edge connectivity plays a pivotal in algorithms to prevent single-point failures, ensuring that signal paths between components remain operational despite defects or breakdowns in interconnects. Fault-tolerant strategies in VLSI multicomputers rely on graphs with minimum edge connectivity to guarantee alternative paths, minimizing downtime in chip-level networks where even minor edge failures can cascade into system-wide issues. This approach has been formalized in designs that compute edge-disjoint paths, enhancing overall circuit reliability without excessive hardware overhead. Social networks, often represented as directed graphs, utilize strong connectivity to model bidirectional information flow, where a strongly connected component ensures that messages can propagate from any node to any other, facilitating efficient dissemination in platforms like online communities. Research on real-world directed networks reveals that strong connectivity correlates with reduced hierarchical barriers, enabling resilient information cascades even under node removals that simulate user dropouts or . This property underpins algorithms for detecting echo chambers or optimizing by identifying maximally strongly connected subgraphs. Recent advancements from 2020 to 2025 have extended connectivity applications to , such as quantum-inspired graph computing for neuromorphic hardware, where algorithms inspired by optimize graph structures to enhance resilience against noise and faults. In wireless ad-hoc networks, resilient routing protocols enhance sensor resilience, allowing to persist despite node mobility or environmental interference in applications like . Network reliability, particularly all-terminal reliability—the probability that a graph remains connected under random edge failures—is a cornerstone of these designs but is computationally #P-hard, necessitating techniques for practical deployment. In biological networks, analyzes connectivity patterns to uncover resilience mechanisms, with studies identifying small-world properties in structural and functional connectomes that buffer against lesions or disorders. A 2019 highlighted how graph metrics like and path length reveal modular connectivity in networks, providing insights into integration across regions. These models have been extended through 2025 with graph neural networks that predict changes in neurodegenerative diseases to preserve cognitive resilience. Computational algorithms for connectivity assessment, such as max-flow variants, aid in simulating these biological graphs efficiently.

References

  1. https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch3.pdf
  2. https://www.jstor.org/stable/2371086
  3. https://www.sciencedirect.com/topics/computer-science/connectivity-graph
  4. http://www.cs.rpi.edu/~goldberg/14-GT/08-block.pdf
  5. https://math.gordon.edu/courses/mat230/handouts/graphs.pdf
  6. https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-fall-2010/e6db7638031b754f5f68012946af4763_MIT6_042JF10_chap06.pdf
  7. https://dspace.mit.edu/bitstream/handle/1721.1/70477/6-042j-fall-2002/contents/readings/ln4.pdf
  8. https://www3.nd.edu/~dgalvin1/40210/40210_F12/CGT_early.pdf
  9. https://link.springer.com/article/10.1007/BF01792729
  10. http://courses.ics.hawaii.edu/ReviewICS241/morea/graphs/Graphs4-QA.pdf
  11. https://mathworld.wolfram.com/ConnectedComponent.html
  12. http://web.stanford.edu/class/archive/cs/cs103/cs103.1204/lectures/10-GraphsI/GraphsI.2.pdf
  13. https://facultyweb.kennesaw.edu/mlavrov/courses/graph-theory/lecture2.pdf
  14. https://mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/11599/selected-solutions.pdf
  15. https://mathworld.wolfram.com/WeaklyConnectedComponent.html
  16. https://mathworld.wolfram.com/StronglyConnectedComponent.html
  17. https://www.zib.de/userpage/groetschel/teaching/WS1314/BondyMurtyGTWA.pdf
  18. https://mathworld.wolfram.com/GraphBridge.html
  19. https://diestel-graph-theory.com/
  20. https://eudml.org/doc/211191
  21. https://doi.org/10.1007/BF01589230
  22. https://www.renyi.hu/~p_erdos/1960-10.pdf
  23. https://arxiv.org/pdf/1207.3319
  24. https://link.springer.com/chapter/10.1007/978-3-319-53004-8_3
  25. https://arxiv.org/pdf/2301.09505
  26. https://arxiv.org/pdf/1202.0319
  27. https://arxiv.org/abs/1811.02664
  28. https://arxiv.org/pdf/2305.16882
  29. https://link.springer.com/article/10.1007/s00373-007-0725-0
  30. http://staff.ustc.edu.cn/~xujm/201003.pdf
  31. https://www.sciencedirect.com/science/article/pii/S0012365X06000689
  32. https://www.sciencedirect.com/science/article/pii/S0012365X08000551
  33. https://www.sciencedirect.com/science/article/pii/S0012365X99900419
  34. https://www.mdpi.com/2073-8994/14/2/304
  35. https://epubs.siam.org/doi/10.1137/0201010
  36. https://dl.acm.org/doi/10.1145/3564246.3584663
  37. https://www.sciencedirect.com/science/article/pii/S1570866708000415
  38. https://inria.hal.science/hal-01422216v1/document
  39. https://omereingold.wordpress.com/wp-content/uploads/2014/10/sl.pdf
  40. https://dl.acm.org/doi/10.1145/1391289.1391291
  41. https://epubs.siam.org/doi/10.1137/S009753979325247X
  42. https://arxiv.org/abs/2510.08297
  43. https://oeis.org/A001187
  44. https://oeis.org/A001349
  45. https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.3240010202
  46. https://web.mat.upc.edu/marc.noy/uploads/2013/05/enhandbook-419-458.pdf
  47. https://www.cambridge.org/core/journals/proceedings-of-the-royal-society-of-edinburgh-section-a-mathematics/article/xixasymptotic-enumeration-of-connected-graphs/52A667D8A325B3213291355139528A8B
  48. https://faculty.etsu.edu/gardnerr/5340/notes-Bondy-Murty-GT/Bondy-Murty-GT-9-1.pdf
  49. https://www.whitman.edu/Documents/Academics/Mathematics/Jones.pdf
  50. https://facultyweb.kennesaw.edu/mlavrov/courses/graph-theory-slides-2.pdf
  51. https://www.itm-conferences.org/articles/itmconf/pdf/2024/01/itmconf_iicma2024_02003.pdf
  52. https://facultyweb.kennesaw.edu/mlavrov/courses/graph-theory/lecture27.pdf
  53. https://math.mit.edu/~goemans/18438F09/OLD/lec3.pdf
  54. https://www.sciencedirect.com/science/article/abs/pii/S1389128611001381
  55. http://snap.stanford.edu/class/cs224w-2017/projects/cs224w-89-final.pdf
  56. https://apps.dtic.mil/sti/pdfs/ADA611771.pdf
  57. https://www.sciencedirect.com/topics/computer-science/fault-tolerant-routing
  58. https://www.pnas.org/doi/10.1073/pnas.2215752120
  59. https://www.nature.com/articles/s41467-025-63494-z
  60. https://www.researchgate.net/publication/396769181_Resilient_routing_in_ad_hoc_wireless_sensor_networks
  61. https://epubs.siam.org/doi/10.1137/18M1201846
  62. https://www.frontiersin.org/journals/neuroscience/articles/10.3389/fnins.2019.00585/full
  63. https://www.mdpi.com/2076-3425/15/1/17
Add your contribution
Related Hubs
User Avatar
No comments yet.