Find a bipartite graph that is not isomorphic to a subgraph of any k-cube
Bipartite graph non-isomorphic to a subgraph of any k-cube
2
$\begingroup$
graph-theory
-
0In 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
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?