In graph theory, the hypercube graph Qn is a regular graph with 2n vertices, 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 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.
Hypercube graphs should not be confused with cubic graphs, which are graphs that are 3-regular. The only hypercube that is a cubic graph is Q3.
Read more about Hypercube Graph: Construction, Problems, Examples
Famous quotes containing the word graph:
“When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.”
—Marshall McLuhan (1911–1980)