Skip to main content
3 of 3
added 130 characters in body
M. Winter
  • 13.6k
  • 3
  • 29
  • 70

Concerning the edges, consider the following:

Let $v\in \smash{\{0,1\}^d}$ be a 0/1-vector with exactly $k$ zeroes. If $v\not=0$, there are exactly $2^k$ 0/1-vectors that have vanishing inner product with $v$. The vector $v=0$ is an exception, as it has zero inner product with itself (this would give a loop otherwise), and so we count only $\smash{2^d-1}$ neighbors for this one. The number of non-edges then is

$$\frac 12 \Big[\sum_{k=0}^d {d\choose k} 2^k-1\Big] = \frac {3^d-1}2.$$

M. Winter
  • 13.6k
  • 3
  • 29
  • 70