Connectivity of Cycles, Wheels, and Cubes

Connectivity Through Paths and Separators

Connectivity measures how many failures a graph can withstand before it breaks apart. To determine a graph’s connectivity exactly, it is useful to give both sides of the argument: show that some small set of vertices or edges disconnects the graph, and prove that no smaller set can do so. Disjoint paths provide a complementary perspective: several routes between vertices can survive some failures, while a separator or cut certifies the limit.

Throughout, graphs are finite and simple. A vertex separator is a set of vertices whose deletion disconnects a graph or leaves at most one vertex. An edge cut is a set of edges whose deletion disconnects a graph. For a connected graph with at least two vertices, its vertex connectivity \(\kappa(G)\) is the minimum size of a vertex separator, and its edge connectivity \(\lambda(G)\) is the minimum size of an edge cut. The convention about leaving at most one vertex gives \(\kappa(K_n)=n-1\), including \(\kappa(K_2)=1\). A path is a sequence of distinct vertices with consecutive vertices adjacent. Paths with the same endpoints are internally vertex-disjoint if no internal vertex of one is an internal vertex of another; they are edge-disjoint if they share no edges.

Cycles

Proof. First consider vertex connectivity. Deleting at most one vertex from a cycle leaves a connected graph: with no deletion it is the cycle, and deleting one vertex leaves a path on the other \(r-1\) vertices. Thus \(\kappa(C_r)\ge2\). For \(r=3\), deleting two vertices leaves one vertex, so it is a separator under the stated convention. For \(r\ge4\), choose a vertex \(v\) and delete its two neighbors. The vertex \(v\) is isolated, and at least one other vertex remains because \(r-3\ge1\). The remaining graph is disconnected, so \(\kappa(C_r)\le2\).

For edge connectivity, deleting the two edges incident with any one vertex isolates that vertex, so \(\lambda(C_r)\le2\). For the lower bound, take any nonempty proper subset \(A\) of the vertices. As one goes around the cycle, membership changes from \(A\) to its complement at least twice: entering \(A\) and leaving it each require a change. Each such change corresponds to an edge crossing between \(A\) and its complement. Therefore every nontrivial partition has at least two crossing edges. Any edge cut must remove all edges crossing the partition of the resulting components, so it has size at least two. Hence \(\lambda(C_r)\ge2\), proving both equalities. \(\square\)

Wheel Graphs

Proof. For vertex connectivity, deleting at most two vertices cannot disconnect the wheel. If the hub remains, every remaining rim vertex is adjacent to it, so all remaining vertices lie in one connected component. If the hub is deleted, at most one additional vertex can be deleted; the rim cycle with at most one vertex removed is connected. Thus \(\kappa(W_r)\ge3\).

For \(r=3\), the graph is \(K_4\), and deleting three vertices leaves one vertex, so \(\kappa(W_3)\le3\). For \(r\ge4\), delete the hub and two nonadjacent rim vertices. The remaining rim vertices split into at least two nonempty path components: for instance, deleting rim vertices \(v_1\) and \(v_3\) leaves \(v_2\) separated from the path \(v_4,\ldots,v_r\). Thus \(\kappa(W_r)\le3\).

For edge connectivity, deleting the three edges incident with a rim vertex isolates it, so \(\lambda(W_r)\le3\). To prove the reverse bound, consider a nonempty proper set \(T\) of rim vertices on one side of a partition, with the hub on the other side. If \(T\) is a proper subset of the rim, at least two rim edges cross between \(T\) and the other rim vertices, by the cycle argument. In addition, each vertex of \(T\) has a spoke to the hub, so at least one spoke crosses. The partition therefore has at least three crossing edges. If \(T\) is the whole rim, all \(r\ge3\) spokes cross. These cases cover every nontrivial partition, after choosing the side not containing the hub; every edge cut must contain all crossing edges for some such partition. Hence \(\lambda(W_r)\ge3\), completing the proof. \(\square\)

Hypercubes

Proof. We first prove the vertex-connectivity lower bound by induction on \(d\): deleting at most \(d-1\) vertices from \(Q_d\) leaves a connected graph. For \(d=1\), \(Q_1\) consists of two vertices joined by one edge, and deleting zero vertices leaves it connected.

Now let \(d\ge2\), and assume the statement for \(Q_{d-1}\). Split \(Q_d\) into two layers according to the last coordinate, each a copy of \(Q_{d-1}\). Each vertex in one layer has exactly one corresponding vertex in the other layer, joined by an edge; these \(2^{d-1}\) edges form a matching between the layers. Let \(S\) be a set of at most \(d-1\) deleted vertices, and let \(S_0,S_1\) be the deletions in the two layers.

If both \(|S_0|\) and \(|S_1|\) are at most \(d-2\), the induction hypothesis says that the surviving vertices in each layer form a connected graph. At most \(|S|\le d-1\) matching edges are blocked by deleted vertices, since each deleted vertex is incident with just one matching edge. There are \(2^{d-1}>d-1\) matching edges, so at least one remains. It joins the two connected surviving layers.

Otherwise, one layer contains at least \(d-1\) deleted vertices. Since \(|S|\le d-1\), all deletions are in that layer, and the other layer is intact and connected. The damaged layer has at least one surviving vertex, because \(2^{d-1}>d-1\). Every surviving vertex there retains its matching edge to the intact layer. Consequently all surviving vertices are connected through that intact layer. This proves the lower bound for vertex connectivity.

For the upper bound, deleting the \(d\) neighbors of any vertex isolates it. For \(d=1\), this deletion leaves a single vertex, which is a separator by convention; for \(d\ge2\), other vertices remain as well. Thus \(\kappa(Q_d)\le d\), and \(\kappa(Q_d)=d\).

It remains to establish the edge-connectivity equality. We prove that every nonempty proper vertex set \(A\) has at least \(d\) edges to its complement, again using induction on \(d\). For \(Q_1\), the only nontrivial partition has one crossing edge. For \(d\ge2\), use the two layers above, and write \(A_0,A_1\) for the portions of \(A\) in those layers. The number of crossing edges is the sum of the crossing edges within the layers and the matching edges whose corresponding vertices have different membership in \(A_0\) and \(A_1\).

If both \(A_0,A_1\) are nonempty proper subsets of their layers, induction gives at least \(d-1\) crossing edges inside each layer, for at least \(2(d-1)\ge d\) in total. If exactly one is a nonempty proper subset and the other is empty or full, there are at least \(d-1\) internal crossing edges in the partial layer and at least one crossing matching edge. If neither is partial, each is empty or full. Since \(A\) is nonempty and proper, one layer must be full and the other empty; all \(2^{d-1}\ge d\) matching edges cross. These cases prove the claimed lower bound on every partition. Any edge cut must remove the crossing edges of a partition into components, so \(\lambda(Q_d)\ge d\). Finally, the \(d\) edges incident with any vertex form an edge cut: deleting them isolates that vertex. Hence \(\lambda(Q_d)\le d\), and \(\lambda(Q_d)=d\). \(\square\)

Reading the Certificates Correctly

For each family, the lower bound rules out a smaller failure set, while the constructed separator or cut proves that the stated value is attainable. In the hypercube, the proof of the vertex lower bound is a deletion argument; the path example makes the corresponding disjoint-route idea concrete for a particular pair. The earlier material on Menger’s theorem explains the general connection between such path packings and separators. Here the direct proofs also show why the connectivity values hold for the entire families, rather than only for the example graphs.

A frequent error is to confuse a vertex separator with an edge cut. For example, in \(W_5\), deleting the three edges \(h1,12,15\) isolates vertex \(1\), but this does not show that the vertex connectivity is three: no vertices have been deleted. To certify \(\kappa(W_5)\le3\), one must give a vertex set, such as \(\{h,2,4\}\), whose deletion disconnects the graph. Conversely, a set of three vertices does not certify an edge-connectivity bound unless the edges removed are specified.

Another error is to establish only a lower or only an upper bound. Showing that a vertex has degree \(d\) gives an edge cut of size \(d\), hence an upper bound on \(\lambda\); it does not rule out a smaller cut. The partition arguments above supply the required lower bounds. In general, an exact connectivity calculation needs both a failure set and an argument that every smaller set leaves the graph connected.