# Vertex Connectivity of the Hypercube [closed]

I am revising my lecture notes about connectivity, but I am stuck regarding proof of $$κ(Q_d) = d$$ Then I took a look of the proof by induction in D. West's book. For $$d\leq1$$, $$Q_d$$ is a clique with $$k+1$$ vertices and connectivity $$k$$.Can anyone visualize that statement about $$k+1$$ vertices? Also, it would be great if you have another proof or explanation to articulate my understanding of it. Thanks

## closed as off-topic by YCor, bof, Chris Godsil, Mark Wildon, Ben BarberNov 27 '18 at 10:30

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – bof, Chris Godsil, Mark Wildon
If this question can be reworded to fit the rules in the help center, please edit the question.

• Did you mean "$Q_d$ is a clique with $d+1$ vertices and connectivity $d$? – bof Nov 24 '18 at 12:52
• What is hard to visualize about the graphs $Q_0=K_1$ and $Q_1=K_2$? – bof Nov 24 '18 at 12:53

You can connect any two vertices by $$d$$ vertex-disjoint paths directly. If they differ in $$k$$ coordinates, $$k$$ paths will be in the $$k$$-cube in which they are opposite (use coordinates in the cyclic order). The rest are formed by moving along extra coordinate axis to an adjacent $$k$$-cube, going to the opposite vertex in it, and moving along the extra axis backwards.
We can define the Hypercube $$Q_{k}$$ recursively, as follows. We let $$Q_{0}=K_{1}$$ and $$Q_{k}=Q_{k-1}\square K_{2}$$, for all $$k\geq1$$. Let us observe that $$Q_{k}$$, $$k\geq1$$, is obtained from two disjoint copies of $$Q_{k-1}$$ by joining their corresponding vertices.
Now, we prove that $$\kappa(Q_{k})=k$$. We proceed by induction on $$k$$. The equality is obvious for $$k=0$$ and $$k=1$$. In such cases the Hypercube is isomorphic to $$K_{1}$$ and $$K_{2}$$, respectively. Now let we have the equality for all Hypercubes of order less that $$k$$ and prove the equality for a Hypercube of order $$k$$. We now consider the Hypercube $$Q_{k}$$. It is well-known that $$\kappa(G)\leq \delta(G)$$, for all graphs $$G$$. Therefore, $$$$\label{Q1} \kappa(Q_{k})\leq \delta(Q_{k})=k.$$$$ Suppose to the contrary that $$\kappa(Q_{k})\leq k-1$$. Let $$G_{1}$$ and $$G_{2}$$ be those two copies of $$Q_{k-1}$$ as subgraphs of $$Q_{k}$$. Let $$S$$ be a $$\kappa(Q_{k})$$-set. We consider two cases.
Case 1. $$S\subseteq V(G_{1})$$ or $$S\subseteq V(G_{2})$$. By symmetry we may assume that $$S\subseteq V(G_{2})$$. Since $$|S|\leq k-1\leq2^{k-1}$$, the graph $$G-S$$ is obtained from a copy of $$Q_{k-1}$$ by adding $$2^{k-1}-|S|$$ new vertices such that every new vertex has exactly one neighbor in $$V(Q_{k-1})$$ (note that there are some possible edges among the new vertices). So, $$G-S$$ is connected which is a contradiction..
Case 2. $$S\cap V(G_{1})\neq\emptyset$$ and $$S\cap V(G_{2})\neq\emptyset$$. Then, $$|S\cap V(G_{1})| and $$|S\cap V(G_{2})|. Therefore, both $$G_{1}'=G_{1}-(S\cap V(G_{1}))$$ and $$G_{2}'=G_{2}-(S\cap V(G_{2}))$$ are connected by the induction hypothesis. On the other hand, there are some edges with one end point in $$V(G_{1}')$$ and the other in $$V(G_{2}')$$. This shows that $$G-S$$ is connected, a contradiction.
Therefore, $$\kappa(Q_{k})=k$$.