Connectivity of bipartite graph. Consider $G(V,E)$ be a bipartite graph with $V_1$ and $V_2$ two parts : $|V_1| = \binom{n}{k}$ and $|V_2| = \binom{n}{k+1}$ and $\forall v \in V_1$ we have $\deg v = n-k$ and $\forall u \in V_2$ $\deg u = k + 1$. After _Misha's_ comment it's better to add some information. Actually $V_1$ is $[n]^i$ and $V_2 = [n]^{i+1}$, i.e. $[n]^i$ is $i$ elemented subset of $\\{1 \dots n\\}$. And $vu$ iff $v \subset u$ (for example $\\{1 \dots i\\} \subset \\{1 \dots i , i + 1\\}$, means there is edge between them) How can we prove that $G$ is connected? I tried to make some induction, but it failed in induction step. Don't know how to step back here. Any hints?

The standard way to prove this is to show that if we take any two vertices $v,w$ in the graph, then there is a path to get from $v$ to $w$.

For this graph, it's enough to get from $v$ to $w$ assuming $v,w \in V_1$, because each vertex in $V_2$ has a neighbor in $V_1$.

I'd first consider a case where $v,w$ are disjoint sets. For example, $n=8$, $k=4$, $v=\\{1,2,3,4\\}$ and $w = \\{5,6,7,8\\}$. Think about what a path would look like in this case.

That's probably the hardest single case to deal with, but it's not fully general, and it's not even necessarily possible for all $n$ and $k$. (If $k > \frac n2$, there are no disjoint pairs like this at all!) Still, once you find this path, you should be able to explain how to find any other path. (Just be sure not to use any elements of $[n]$ other than the ones found in $v \cup w$, because you can't assume that any such elements exist.)