Hypercube contained in complete bipartite graph

166 Views Asked by At

I am trying to solve a problem where I have to show that a particular unlabeled biclique denoted $K_{r,s}$, where $r$ and $s$ denotes the number of vertices in each biclique, is not contained in any hypercube $Q_{k}$. In my situation r =2 and s = 3. I am not asking for a complete solution, I am just confused about the question since I don't understand how one shows that a particular graph is contained inside / not contained inside another graph.

The wikipedia article about hypercubes mentions some characteristics about the number of vertices, edges, diameter etc. about the hypercube. The only thing I can think of is that some of those characteristics might be helpful?

1

There are 1 best solutions below

3
On BEST ANSWER

As it states in the Wikipedia article you are referring to, the vertices of $Q_k$ can be identified with binary strings of length $k$, where two vertices are adjacent if their Hamming distance is 1, i.e. if the two strings differ at one position.

If $K_{2, 3}$ is a subgraph of some $Q_k$, then some two vertices in $V(Q_k)$ have three neighbours in common. We show this is impossible.

Let $0^m$ denote a string of $m$ zeros. Without loss of generality, consider a vertex $v$ and its neighbour $a$ represented by $0^k$ and $10^{k-1}$ respectively. Consider $u$ a neighbour of $a$ distinct from $v$. By definition, the representation of $u$ contains exactly two 1s, say that the 1s are at position $i$ and $j$, with $1\leq i<j\leq k$. Thus, it is represented by $0^{i-1}10^{j-i-1}10^{k-j}$. However, the only strings with Hamming distance 1 from $0^k$ and $0^{i-1}10^{j-i-1}10^{k-j}$ are $0^{i-1}10^{k-i}$ and $0^{j-1}10^{k-j}$. Thus, any two vertices in $Q_k$ have at most two neighbours in common (in fact, they have exactly two neighbours in common). Thus, $K_{2, 3}$ is not a subgraph of $Q_k$ for any $k\geq 0$.