Hypercube graph
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 Qn 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 2n 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 Qn is incident to exactly n edges (that is, Qn 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 2n−1n.

The name comes from the fact that the hypercube graph is the one-dimensional skeleton of the geometric 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.