# n-cube connectivity problem

Given $n\geq 2$, let us consider the n-cube $H_n=(V,E)$, i.e. vertex set $V$ is $\{0,1\}^n$. Here, the edges of $H_n$ are directed, oriented by set inclusion, i.e., $(x,y)\in E$ iff $x\subseteq y$ and $\text{dist}_{Hamm}(x,y)=1$). Let $0^n := (0, 0, \ldots, 0)$ and $1^n := (1, 1, \ldots, 1)$. Let $S\subseteq V\setminus \{0^n, 1^n\}$ such that $|S|=n$. Assume that in $H_n\setminus S$ there is no directed path from $0^n$ to $1^n$. Then, is it true that $H_n\setminus S$, now viewed as undirected graph, is disconnected (i.e. "no directed path" implies "no undirected path" in this setting) ?

• What is the orientation of the edges, even for $H_3$? The $n-1$ dimensional faces of $H_n$ inherit an orientation from $H_n$, but already the $n-2$ dimensional edges inherit opposite orientations from the two adjacent $n-1$ dimensional faces. Also, do you want to assume $0^n,1^n\notin S$? – Joonas Ilmavirta Nov 27 '14 at 9:49
• the orientation is by set inclusion: (x,y)\in E iff x\subset y and hamming_dist(x,y)=1. And yes $0^n,1^n$ are not in $S$. Thank you. – Xorwell Nov 27 '14 at 9:55

Every vertex removed from the $k$th layer prohibits $k!(n-k)!\leq (n-1)!$ paths. Thus, if $n$ removed verices prohibit all $n!$ paths, then each of them prohibits exactly $(n-1)!$ paths, and the sets of prohibited paths are disjoint. This means that either all the vertices are on the first layer, or all the vertices are on the $(n-1)$th layer. In both cases their removal disconnects the unoriented graph as well.