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) ? 



n-cube connectivity problem
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.


