136 Connectivity
136.1 Connectivity
A vertex cut: a proper subset S whose deletion leaves G disconnected.
A vertex cut of \(G\) is a subset \(V'\) of \(V\) such that \(G - V'\) is disconnected. A \(k\)-vertex cut is a vertex cut of \(k\) elements. A complete graph has no vertex cut; in fact, the only graphs which do not have vertex cuts are those that contain complete graphs as spanning subgraphs.
An edge cut: a set of edges of G whose deletion leaves G disconnected.
Recall that an edge cut of \(G\) is a subset of \(E\) of the form \([S, \bar{S}]\), where \(S\) is a nonempty proper subset of \(V\). A \(k\)-edge cut is an edge cut of \(k\) elements. If \(G\) is nontrivial and \(E'\) is an edge cut of \(G\), then \(G - E'\) is disconnected.
Vertex connectivity \(\kappa \)(G). If a vertex cut exists it is the minimum cut size; otherwise (complete graphs) it is \(\nu \) \(-\) 1.
If \(G\) has at least one pair of distinct nonadjacent vertices, the connectivity \(\kappa (G)\) of \(G\) is the minimum \(k\) for which \(G\) has a \(k\)-vertex cut; otherwise, we define \(\kappa (G)\) to be \(\nu - 1\). Thus \(\kappa (G) = 0\) if \(G\) is either trivial or disconnected.
Edge connectivity \(\kappa \)’(G): the minimum size of an edge cut (sInf \(\emptyset \) = 0).
we then define the edge connectivity \(\kappa '(G)\) of \(G\) to be the minimum \(k\) for which \(G\) has a \(k\)-edge cut. If \(G\) is trivial, \(\kappa '(G)\) is defined to be zero. Thus \(\kappa '(G) = 0\) if \(G\) is either trivial or disconnected, and \(\kappa '(G) = 1\) if \(G\) is a connected graph with a cut edge.
G is k-connected.
\(G\) is said to be \(k\)-connected if \(\kappa (G) \geq k\). All nontrivial connected graphs are 1-connected.
G is k-edge-connected.
\(G\) is said to be \(k\)-edge-connected if \(\kappa '(G) \geq k\). All nontrivial connected graphs are 1-edge-connected.
v is a cut vertex: G is connected but deleting v disconnects it.
A vertex \(v\) of \(G\) is a cut vertex if \(E\) can be partitioned into two nonempty subsets \(E_1\) and \(E_2\) such that \(G[E_1]\) and \(G[E_2]\) have just the vertex \(v\) in common. If \(G\) is loopless and nontrivial, then \(v\) is a cut vertex of \(G\) if and only if \(\omega (G - v) \gt \omega (G)\).
A block: connected with no cut vertex.
A connected graph that has no cut vertices is called a block. Every block with at least three vertices is 2-connected. A block of a graph is a subgraph that is a block and is maximal with respect to this property. Every graph is the union of its blocks.
Two u–v walks are internally disjoint if they share no internal vertex.
A family of paths in \(G\) is said to be internally-disjoint if no vertex of \(G\) is an internal vertex of more than one path of the family.
A finite family of u–v walks, pairwise internally disjoint (family form, for Menger).
Edge subdivision: replace e = uv by a length-2 path through a new vertex.
It is convenient, now, to introduce the operation of subdivision of an edge. An edge \(e\) is said to be subdivided when it is deleted and replaced by a path of length two connecting its ends, the internal vertex of this path being a new vertex.
Let \(G\) be a finite simple graph with at least one vertex. Then the edge connectivity of \(G\) is at most its minimum degree; that is, \(\kappa '(G) \le \delta (G)\), where \(\delta (G)\) denotes the least degree of any vertex of \(G\).
Let \(G\) be a finite simple graph on \(n\) vertices. Then its vertex connectivity satisfies
Let \(G\) be a finite simple graph on a vertex set with at least three vertices. If \(G\) is connected and has no cut vertex, then its vertex connectivity satisfies \(\kappa (G) \ge 2\).
Let \(G\) be a finite simple graph. If the edge connectivity of \(G\) vanishes, \(\kappa '(G) = 0\), then its vertex connectivity also vanishes, \(\kappa (G) = 0\).
Let \(G\) be a finite simple graph whose edge connectivity satisfies \(\kappa '(G) = k+1\) for some natural number \(k\). Then \(G\) has an edge \(e\) whose deletion yields a graph \(G - e\) with \(\kappa '(G - e) = k\).
Let \(G\) be a finite simple graph on a vertex set \(V\), and let \(e\) be an unordered pair of vertices; write \(G - e\) for the graph obtained from \(G\) by deleting the edge \(e\) (leaving \(G\) unchanged if \(e\) is not an edge of \(G\)). Then the vertex connectivities satisfy
Let \(G\) be a connected simple graph on a finite vertex set \(V\) with at least three vertices, and suppose the edge \(\{ u,v\} \) of \(G\) is a bridge (that is, deleting it disconnects \(G\)). Then \(G\) has a cut vertex: there exists a vertex \(w\) such that the singleton \(\{ w\} \) is a vertex cut of \(G\), meaning \(\{ w\} \) is a proper subset of \(V\) and the graph \(G - w\) obtained by deleting \(w\) is disconnected.
For any finite simple graph \(G\), the vertex connectivity is at most the edge connectivity:
For every finite nonempty simple graph \(G\), the vertex connectivity, edge connectivity, and minimum degree satisfy
where \(\kappa (G)\) is the least size of a vertex cut (or \(|V(G)| - 1\) when \(G\) has no vertex cut), \(\kappa '(G)\) is the least size of an edge cut, and \(\delta (G)\) is the minimum degree of a vertex of \(G\).
Let \(G\) be a finite simple graph on a vertex set \(V\), let \(s \subseteq V\), and let \(u, v \in s\). If there is a walk \(p\) from \(u\) to \(v\) in \(G\) every vertex of which lies in \(s\), then \(u\) and \(v\), regarded as vertices of the induced subgraph \(G[s]\), are reachable from one another in \(G[s]\); that is, some walk joins them within \(G[s]\).
Let \(G\) be a finite graph on at least three vertices whose connectivity satisfies \(\kappa (G) \ge 2\). Then for any two distinct vertices \(u\) and \(v\) there exist two \(u\)–\(v\) paths in \(G\) that are internally disjoint and, moreover, share no edge.
Let \(G\) be a finite simple graph on a vertex set of at least three vertices. Then the vertex connectivity satisfies \(\kappa (G) \ge 2\) if and only if for every pair of distinct vertices \(u, v\) there exist two internally disjoint \(u\)–\(v\) paths, that is, two paths from \(u\) to \(v\) whose only common vertices are the endpoints \(u\) and \(v\).
Let \(G\) be a finite simple graph whose vertex connectivity satisfies \(\kappa (G) \ge 2\). Then for any two distinct vertices \(u\) and \(v\) of \(G\) there is a cycle of \(G\) whose support contains both \(u\) and \(v\).
Let \(G\) be a finite block — a connected graph with no cut vertex — on at least three vertices. Then any two distinct edges \(e_1\) and \(e_2\) of \(G\) lie on a common cycle; that is, there is a cycle in \(G\) whose edge set contains both \(e_1\) and \(e_2\).
Let \(G\) be a block on a vertex set of at least three vertices; that is, \(G\) is connected and has no cut vertex. Then the vertex connectivity of \(G\) satisfies \(\kappa (G) \ge 2\).
The Harary graph H_{m,n} on vertex set ZMod n (a circulant).
We shall show that equality holds in (3.1) by constructing an \(m\)-connected graph \(H_{m,n}\) on \(n\) vertices that has exactly \(\{ mn/2\} \) edges. The structure of \(H_{m,n}\) depends on the parities of \(m\) and \(n\); there are three cases. Case 1 \(m\) even. Let \(m = 2r\). Then \(H_{2r,n}\) is constructed as follows. It has vertices \(0, 1, \ldots , n-1\) and two vertices \(i\) and \(j\) are joined if \(i - r \leq j \leq i + r\) (where addition is taken modulo \(n\)). Case 2 \(m\) odd, \(n\) even. Let \(m = 2r + 1\). Then \(H_{2r+1,n}\) is constructed by first drawing \(H_{2r,n}\) and then adding edges joining vertex \(i\) to vertex \(i + (n/2)\) for \(1 \leq i \leq n/2\). Case 3 \(m\) odd, \(n\) odd. Let \(m = 2r + 1\). Then \(H_{2r+1,n}\) is constructed by first drawing \(H_{2r,n}\) and then adding edges joining vertex 0 to vertices \((n-1)/2\) and \((n+1)/2\) and vertex \(i\) to vertex \(i+(n+1)/2\) for \(1 \le i \lt (n-1)/2\).
Let \(n \ge 1\) and let \(m\) be a natural number with \(m \lt n\). Then the Harary graph \(H_{m,n}\) on \(n\) vertices has vertex connectivity \(\kappa (H_{m,n}) = m\) (Harary, 1962).
Let \(m\) and \(n\) be natural numbers with \(n \ge 1\) and \(m \lt n\), and let \(H_{m,n}\) be the Harary graph on the \(n\) vertices \(\mathbb {Z}/n\mathbb {Z}\). Then \(H_{m,n}\) has exactly \(\lceil mn/2 \rceil \) edges (equivalently, \(\lfloor (mn+1)/2 \rfloor \)).
Let \(G\) be a finite simple graph with vertex set \(V\) and edge set \(E\), and let \(\kappa '(G)\) denote its edge connectivity. For every natural number \(k\) with \(k \le \kappa '(G)\),
Let \(G\) be a finite simple graph on \(\nu \) vertices with minimum degree \(\delta \) and vertex connectivity \(\kappa (G)\). If \(\delta \ge \nu - 2\), then \(\kappa (G) = \delta \).
Let \(G\) be a finite simple graph that is \(3\)-regular, meaning every vertex has exactly three neighbours. Then the vertex connectivity and the edge connectivity of \(G\) coincide, \(\kappa (G) = \kappa '(G)\).
Let \(G\) be a finite simple graph with edge connectivity \(\kappa '(G)\). Then \(\kappa '(G) \ge 2\) if and only if for every pair of distinct vertices \(u\) and \(v\) there exist two paths from \(u\) to \(v\) whose edge sets are disjoint.