Let a hypercube be of dimension p. Find the maximum number of nodes (on vertices) for which no vertex is connected via edge to more than one node. Note: it is ok if some vertices do not have connections to nodes.
I really have no idea how to start this problem so please help in any way. Also, a general pattern for p would be really useful. Thanks so much in advance!!!
I started to solve this problem as follows.
Let $G$ be a graph whose set $V$ of vertices are is the set of vertices of the hypercube. Two distinct vertices of $G$ are adjacent iff they can be connected in the hypercube by a path consisting of exactly two edges. Remark that $G$ is a regular graph with vertex degree $d={p \choose 2}$. Then your problem is equivalent to find size $i(p)$ of a maximum independent set of vertices of $G$. Let $I$ be any maximal independent set of vertices of $G$. Since each vertex of $V\setminus I$ is adjacent to at least one and at most $s$ vertices of $I$ and any vertex of $I$ is adjacent to exactly $d$ vertices in $V\setminus I$, we have $|V|\le |I|+d|I|$, and $|V\setminus I|\ge \tfrac{d|I|}{d}$, that is $\tfrac{2^{p+1}}{p(p+1)}=\tfrac {|V|}{d+1}\le |I|\le \tfrac {|V|}{2}=2^{p-1}$.
We can compute $i(p)$ for small $p$. It is easy to check that for $2\le p\le 3$, $G$ is a union of two complete graphs $K_{2^{p-1}}$, so $i(2)=i(3)=2$. For $p=4$, $G$ is a union of two graphs with $8$ vertices and degree $6$ each, so their maximal independent subset has size $2$ and so $i(4)=4$.