How Many Edges Hath A Hypercube?

What is really asked when one asks for the number of edges of a hypercube? First off, let us say what we mean by a hypercube. Given a length k, a cube of n dimensions, where n is a positive integer, is the figure formed by two congruent cubes of n-1 dimensions and line segments of length k connecting the corresponding vertices of the two congruent cubes of n-1 dimensions such that each of these line segments is perpendicular to each line segment in the cube of n-1 dimensions which connects one of its endpoints with another vertex of the cube. We also define the special case where n=0, in which case the cube of zero dimensions is a point, which point is its only vertex. Each line segment which connects two vertices of the cube of n dimensions is an edge. A hypercube is a cube of four dimensions. Notice that not all vertices are connected by edges. Also notice that for ease of definition, I am defining cubes as wire frames; wind blows through them. Finally, for ease of notation I will sometimes write "n-cube" to mean the cube of n dimensions.

Let's see some applications of this. First, the cube of 0 dimensions, by definition:

Next, we follow the definition's recipe for finding a 1-cube. What we need is a figure where two 0-cubes, or points, which are congruent (as are all points) are connected with a line segment of length k, such that all other edges blah blah blah, but there are no other edges, so it's just a line segment, basically. Let's name our endpoints P and Q.



			*--------------*
			 P              Q		

PQ=k, because we said so.

Things really get interesting when it comes time to look a a 2-cube, because for the first time the cube of n-1 dimensions has edges, and the perpendicularity of our new edges comes into play. The definition tells us that we will need two congruent 1-cubes:


			*--------------*
			 P              Q		






			*--------------*
			 R              S

RS=PQ=k, because that's what congruency of line segments means. Now we connect the corresponding vertices (P to R and Q to S) such that PR and QS are perpendicular to all segments connecting vertices in the original n-1-cube. In our case, there aren't that man perpendicularities to account for.


			*--------------*
			|P           |_|Q		
			|              |
			|              |
			|              |
			|              |
			|_            _|
			| |          | |
			*--------------*
			 R              S

Due to the limitations of ASCII email, we can stop here, having gotten the flavor of the definition I'm working with without unwisely overstepping the rendering power of this medium.

Now, in order to actually tackle the problem of edge-counting, let's first look at the issue of vertex-counting. We know that the only new vertices introduced in each successive dimension are in a copy of the cube of n-1 dimensions. We can reasonably conclude that the following function V() will return the correct number of vertices for a cube of n dimensions.

    
             _
            / n>=1:  2 * V(n-1)
            |
    V(n) = <
            |
            \ n=0: 1
             -

This is an overblown way of saying that V(n) = 2^n.

So, now we are ready to directly concern ourselves with the problem of edge-counting. First of all, what has our definition to tell us about edges? Well, we know that contained in the new figure are two copies of the old figure. Intuitively, it seems reasonable then to assume that the number of edges is greater than or equal to the number of edges for an n-1 cube. Also, we know that there are some new edges added for each dimension. How many? Well, the definition stated it in a round about way, but since corresponding vertices of the n-1-cube are the ones connected by these edges, those added edges are equal in number to the number of vertices of the n-1-cube. So, we can define a function E to give the number of edges for a cube of n dimensions:

             _
            / n>1:  2 * E(n-1) + V(n-1)
            |
    E(n) = < 
            |
            \ n<=1: n
             -

For a hypercube, ie a 4-cube, E(4) = 32.

Keith_Adams@brown.edu