# Chapter 46. Vertex Connectivity # Chapter 46. Vertex Connectivity Vertex connectivity measures how strongly a graph remains connected when vertices are removed. In earlier chapters, connectivity meant that every pair of vertices was joined by a path. Vertex connectivity refines this idea. It asks how many vertices must fail, be deleted, or be blocked before the graph falls apart. A graph may be connected but fragile. If one important vertex lies between two large parts of the graph, removing that vertex disconnects the graph. Another graph may remain connected even after several vertices are removed. Vertex connectivity distinguishes these cases. ## 46.1 Separating Sets Let \(G = (V,E)\) be a graph. If \(S \subseteq V\), then \(G - S\) denotes the graph obtained by deleting all vertices in \(S\), together with every edge incident to a deleted vertex. A set \(S \subseteq V\) is called a separating set, or vertex cut, if removing \(S\) disconnects the graph. Thus \(S\) is a separating set when \(G - S\) has more connected components than \(G\). For a connected graph, this means simply that \(G - S\) is disconnected. For example, suppose a graph consists of two triangles sharing a single common vertex. The shared vertex is the only passage from one triangle to the other. Removing it separates the graph into two components. Hence the one-element set containing that vertex is a separating set. A vertex cut describes a structural weakness in a graph. It identifies a set of vertices whose removal destroys communication between parts of the graph. ## 46.2 Cut Vertices A vertex \(v\) is called a cut vertex, or articulation vertex, if the set \(\{v\}\) is a separating set. Equivalently, \(v\) is a cut vertex if deleting \(v\) increases the number of connected components. Cut vertices are the simplest kind of vertex failure. They appear naturally in tree-like structures. Every non-leaf vertex of a tree can be a cut vertex when it lies between two branches. In a path graph $$ P_n = v_1v_2\cdots v_n, $$ each internal vertex \(v_2,\ldots,v_{n-1}\) is a cut vertex. Removing such a vertex breaks the path into two smaller paths. By contrast, a cycle graph has no cut vertex. If one vertex is removed from a cycle, the remaining graph is still a path, hence still connected. This contrast is one of the first indications that cycles provide redundancy. A path gives only one route between distant vertices. A cycle gives two directions around the graph. ## 46.3 Vertex Connectivity The vertex connectivity of a graph \(G\), denoted $$ \kappa(G), $$ is the minimum size of a vertex cut. For a connected graph that is not complete, \(\kappa(G)\) is the least number of vertices whose deletion disconnects the graph. This agrees with the standard definition of vertex connectivity as the size of a smallest vertex cut. Complete graphs require a convention, since no proper set of vertices disconnects them; the usual convention is \(\kappa(K_n)=n-1\). Thus \(\kappa(G)\) measures the minimum number of vertex failures needed to destroy connectivity. If \(\kappa(G)=0\), then \(G\) is disconnected. If \(\kappa(G)=1\), then \(G\) is connected but has a cut vertex. If \(\kappa(G)\ge 2\), then no single vertex can disconnect \(G\). More generally, if \(\kappa(G)\ge k\), then the graph remains connected after deleting any set of fewer than \(k\) vertices. ## 46.4 \(k\)-Connected Graphs A graph \(G\) is called \(k\)-connected if $$ \kappa(G) \ge k. $$ Equivalently, \(G\) is \(k\)-connected when no set of fewer than \(k\) vertices disconnects it. A connected graph with at least two vertices is \(1\)-connected. A graph is \(2\)-connected when it remains connected after the deletion of any one vertex. In many texts, a \(2\)-connected graph is also called biconnected. More generally, \(k\)-connected means that vertex connectivity is at least \(k\). The phrase "\(k\)-connected" gives a lower bound, not an exact value. If a graph is \(4\)-connected, then it is also \(3\)-connected, \(2\)-connected, and \(1\)-connected. This convention is common in graph theory. It allows higher connectivity to imply all weaker forms of connectivity. ## 46.5 Examples The path graph \(P_n\), for \(n \ge 3\), has $$ \kappa(P_n)=1. $$ Deleting an internal vertex disconnects it. No deletion of zero vertices can disconnect a connected graph, so the minimum is \(1\). The cycle graph \(C_n\), for \(n \ge 3\), has $$ \kappa(C_n)=2. $$ Deleting one vertex leaves a path, which is connected. Deleting two suitable vertices disconnects the graph. The complete graph \(K_n\) has $$ \kappa(K_n)=n-1. $$ As long as at least two vertices remain, they are adjacent. Therefore the graph cannot be disconnected until all but one vertex have been removed. The complete bipartite graph \(K_{m,n}\) has $$ \kappa(K_{m,n})=\min(m,n), $$ for positive \(m\) and \(n\). Removing all vertices from the smaller part isolates the vertices in the other part. Fewer removals cannot destroy all cross-connections. These examples show how vertex connectivity captures redundancy in routes through vertices. ## 46.6 Connectivity and Minimum Degree Let \(\delta(G)\) denote the minimum degree of \(G\). Then $$ \kappa(G) \le \delta(G). $$ This inequality is fundamental. A graph cannot be more vertex-connected than its least connected vertex allows. To see why, choose a vertex \(v\) of minimum degree. Delete all neighbors of \(v\). If \(G\) is not complete, then \(v\) becomes isolated from the rest of the graph. Hence the set of neighbors of \(v\) is a vertex cut. Its size is \(\deg(v)=\delta(G)\). Therefore the smallest possible vertex cut has size at most \(\delta(G)\). There is also a related inequality involving edge connectivity \(\lambda(G)\): $$ \kappa(G) \le \lambda(G) \le \delta(G). $$ This is often called Whitney's inequality. It says that vertex connectivity is at most edge connectivity, and edge connectivity is at most minimum degree. The inequality can be strict. A graph may have large minimum degree while still having a small vertex cut. Local density does not always imply global robustness. ## 46.7 Biconnected Graphs A graph is biconnected if it is \(2\)-connected. For graphs with at least three vertices, this means that the graph is connected and has no cut vertex. Cycles are the basic examples of biconnected graphs. Complete graphs \(K_n\), for \(n \ge 3\), are also biconnected. A tree with at least three vertices is never biconnected, because every internal branching point or internal path vertex is a cut vertex. Biconnected graphs are important because they represent the first level of vertex redundancy. Between different parts of a biconnected graph, no single vertex controls all communication. In network language, a biconnected graph tolerates the failure of any one vertex without losing connectivity. ## 46.8 Blocks A block is a maximal connected subgraph with no cut vertex. Blocks decompose a connected graph into pieces that are internally robust. Cut vertices may belong to more than one block, and they serve as joints between blocks. For example, in a graph made from two cycles sharing one vertex, each cycle is a block. The shared vertex is a cut vertex of the whole graph, but each cycle separately has no cut vertex. This decomposition is useful because it separates local robustness from global fragility. A graph may contain highly connected regions joined by a small number of articulation points. ## 46.9 Menger's Theorem for Vertex Connectivity Vertex connectivity can also be described by the number of internally disjoint paths between vertices. Two paths from \(u\) to \(v\) are internally vertex-disjoint if they share no vertices except their endpoints \(u\) and \(v\). Menger's theorem states that a graph with at least \(k+1\) vertices is \(k\)-connected if and only if every pair of distinct vertices is joined by at least \(k\) internally vertex-disjoint paths. This theorem is central because it connects two viewpoints: | Cut viewpoint | Path viewpoint | |---|---| | Connectivity is hard to destroy | Many independent routes exist | | Remove vertices to separate the graph | Find paths avoiding shared internal vertices | | Measures vulnerability | Measures redundancy | For \(k=2\), the theorem says that a graph is biconnected precisely when every pair of vertices has two internally disjoint paths between them. This gives a geometric picture of robustness. A single internal vertex cannot block all routes if at least two independent routes exist. ## 46.10 Local and Global Connectivity The vertex connectivity \(\kappa(G)\) is a global invariant. It gives one number for the whole graph. There is also a local version. For two distinct nonadjacent vertices \(u\) and \(v\), let \(\kappa(u,v)\) be the minimum number of vertices whose removal separates \(u\) from \(v\). Then global vertex connectivity can be understood as the smallest such local separation over pairs of vertices. This local view is often more informative. A graph may be very robust in one region and fragile in another. The global value records the weakest separation. In applications, this matters. A communication network may have dense clusters but only one or two gateway machines between regions. Its minimum vertex cut may be small even when most vertices have large degree. ## 46.11 Algorithms Testing vertex connectivity is a basic algorithmic problem. For \(1\)-connectivity, one graph traversal is enough. A graph is connected if breadth-first search or depth-first search reaches every vertex. For \(2\)-connectivity, depth-first search can find all cut vertices in linear time. This gives a linear-time test for whether a graph is biconnected. The same family of DFS techniques is used to find bridges and articulation points. For general \(k\), vertex connectivity can be computed using reductions to flow or cut problems. One common method replaces each vertex by an in-vertex and an out-vertex connected by a capacity-one edge. Then vertex cuts become edge cuts in an auxiliary flow network. The basic idea is this: | Graph problem | Flow interpretation | |---|---| | Remove vertices | Cut capacity-one vertex-splitting edges | | Separate \(s\) from \(t\) | Compute an \(s\)-\(t\) minimum cut | | Find disjoint routes | Compute maximum flow | This method reflects Menger's theorem. Minimum separating sets and maximum families of internally disjoint paths are dual descriptions of the same structure. ## 46.12 Vertex Connectivity in Networks Vertex connectivity has a direct interpretation in networks. If vertices represent routers, stations, people, servers, or cities, then \(\kappa(G)\) measures how many such objects must fail before the network can become disconnected. A network with \(\kappa(G)=1\) has a single point of failure. A network with \(\kappa(G)=2\) has no single point of failure but may fail after two vertex removals. A network with larger connectivity has stronger structural redundancy. However, vertex connectivity is a worst-case measure. It assumes that an adversary or worst-case failure can choose the most damaging vertices. Random failures may behave differently. A graph with one small cut may still perform well under random deletion if that cut is unlikely to fail. Thus vertex connectivity is best understood as a structural guarantee rather than an average-case prediction. ## 46.13 Common Mistakes One common mistake is to confuse vertex connectivity with minimum degree. A high minimum degree helps, but it does not guarantee high vertex connectivity. Another mistake is to confuse edge cuts with vertex cuts. Edge connectivity measures how many edges must be removed. Vertex connectivity measures how many vertices must be removed. Removing one vertex may remove many incident edges at once. A third mistake is to think that a graph with no bridge must be biconnected. This is false. Two cycles sharing one vertex have no bridge, but the shared vertex is a cut vertex. A fourth mistake is to treat \(k\)-connected as meaning exactly \(k\). It means at least \(k\). ## 46.14 Summary Vertex connectivity measures the resistance of a graph to vertex deletion. It is defined by the size of a smallest vertex cut. The main ideas are: | Concept | Meaning | |---|---| | Vertex cut | A set of vertices whose deletion disconnects the graph | | Cut vertex | A single vertex whose deletion disconnects the graph | | \(\kappa(G)\) | Size of a smallest vertex cut | | \(k\)-connected | Remains connected after deleting fewer than \(k\) vertices | | Biconnected | Connected and has no cut vertex | | Menger's theorem | \(k\)-connectivity equals the existence of \(k\) internally disjoint paths | Vertex connectivity is one of the fundamental measures of graph robustness. It connects structural graph theory, path systems, network reliability, and graph algorithms.