Let $m$ be a large integer. Let $G$ a graph with vertex set $V= \{0,1\}^m$ in which two vertices $x,y \in V$ are adyacent if the Hamming distance between $x$ and $y$, which is the number de coordinates in which they differ, is at most $m/2$. The number of vertices of $G$ is $n=2^m$. Show that every vextex in $G$ has degree at least $n/2-1$.
Any help? I think that by symmetry argument you can conclude but i am not sure.
1 Answer
each vertex $v$ is connected to all vectors differ from it in at most $m/2$ coordinates. for each $1\leq k$, there are $m \choose k$ vertices that have distance $k$ from $v$ (choose $k$ coordinates from $m$, then take the vector that differs from $v$ only in these $k$ coordinates, you get a vector with distance $k$ from $v$). so, the number of neighbors of $v$ is:
$ N(v) = {m \choose 1} + {m \choose 2} + ... + {m \choose m/2} = {m \choose 0} + {m \choose 1} +...+ {m \choose m/2} - 1 \geq 1/2 * ({m \choose 0}+...+{m \choose m})-1 = (1/2 * 2^m) -1 = n/2 -1$
