hypercube graph

We define the $d$ th hypercube graph $H_{d}$ to be the 1-skeleton on the $d$ -dimensional cube.

Properties

It has $2^{d}$ vertices and is a $d$ -regular graph.
$H_{d} = (\cdot - \cdot)^{d}$ as a product of graphs
- As a consequence, its spectrum is given by $\pm 1 \pm 1 \dots \pm 1$ d times.
- The number of spanning trees is then $\frac{1}{2^{d}} \prod_{i = 1}^{d} (2^{i})^{(\binom{d}{i})} = 2^{2^{d} - d - 1} \prod_{i = 1}^{d} i^{(\binom{d}{i})}$ by applying Kirchoff's matrix tree theorem +6