Hypercube graph

Overview

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*is a regular graph

_{n}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

^{n}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*is incident to exactly

_{n}*n*edges (that is,

*Q*is

_{n}*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−1}

*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.