Find a bipartite graph that is not isomorphic to a subgraph of any k-cube
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Here's a hint:
Note that the $k$-cube can be represented with nodes the $k$ length strings of $0$s and $1$s, where two nodes are adjacent if they differ in exactly one point. Consider the points $(1,0, \dots ,0)$, and $(0,1, 0, \dots ,0)$. How many points in any $k$-cube are adjacent to both of those points?