How many verticies, edges and faces (cells) does an nd hypercube have

geometrygraph theory

So I guess a 1d hypercube is a line segment. It has 2 verticies and 1 edge. Not sure how many faces it has?

A 2d hypercube is a square. It has 4 verticies and 4 edges. Again not sure how many faces it has?

A 3d hypercube is a cube. It has 8 verticies and 12 edges and 6 faces.

A 4d hypercube has 16 verticies and not sure how many edges or 3d faces.

We can define the faces of an nd hypercube as being (n-1)d hypercubes. So the faces of a cube are squares.

An nd hypercube has $2^n$ verticies. (If we imagine a vertex coordinate $v = (v_1, v_2, …, v_n)$ then choose some subset and set them to $1$, set the rest to $-1$. This describes one vertex. There are $2^n$ subsets of $n$ items.)

How many edges does it have as a function of n? How do you derive that?

How many $(n-1)$d faces does it have? How do you derive that?

Update

For the faces I think we can say: pick a dimension $i$, partition the verticies into two sets of $2^{n-1}$ verticies. One with $v_i = -1$ and the other with $v_i = 1$. Each of these two sets describes a face. There are $n$ ways to pick $i$. So an nd hypercube has $2n$ faces. So a line segment has 2 faces (which are points). A square has 4 faces (which are lines). A cube has 6 faces (which are squares). A 4d hypercube has 8 faces (which are cubes). and so on.

So just edges remains.

Best Answer

Here are a couple hints. I will consider the vertices to be length-$n$ bitstrings.

An edge connects two vertices if the vertices differ by a single bit flip. How many edges are incident to a given vertex? If you multiply this by the number of vertices, what would you do next to end up with the total number of edges?

A facet (i.e. $(n-1)$-dimensional cell) may be chosen by first picking a coordinate, fixing its bit, and then letting all the other bits be arbitrary. How many ways are there to do this?

Related Question