# Bipartite graph non-isomorphic to a subgraph of any k-cube

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

-
Welcome to MSE. Wording your questions in a Polite Language will be appreciated and welcome on this forum. Show us what you have done. Also, tell us if it's a homework and if so, add the (homework) tag. –  user21436 Feb 23 '12 at 0:54
In addition, showing what you already know (or think) about the problem will allow the community to help you more effectively. –  Austin Mohr Feb 23 '12 at 1:13

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?