2
$\begingroup$

Find a bipartite graph that is not isomorphic to a subgraph of any k-cube

  • 0
    In addition, showing what you already know (or think) about the problem will allow the community to help you more effectively.2012-02-23

1 Answers 1

3

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?