In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, the hypercube graph Q_n is a regular graph

Regular graph

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...

 with 2ⁿ vertices

Vertex (graph theory)

In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...

, which correspond to the subsets of a set with n elements.
Two vertices labelled by subsets W and B are joined by an edge if and only if W can be obtained from B by adding or removing a single element.

Each vertex of Q_n is incident to exactly n edges (that is, Q_n is n-regular), so, by the handshaking lemma

Handshaking lemma

In graph theory, a branch of mathematics, the handshaking lemma is the statement that every finite undirected graph has an even number of vertices with odd degree...

 the total number of edges is 2ⁿ⁻¹n.

The name comes from the fact that the hypercube graph is the one-dimensional skeleton of the geometric hypercube

Hypercube

In geometry, a hypercube is an n-dimensional analogue of a square and a cube . It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, perpendicular to each other and of the same length.An...

.

Hypercube graphs should not be confused with cubic graph

Cubic graph

In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs....

s, which are graphs that are 3-regular.