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:
“In this Journal, my pen is a delicate needle point, tracing out a graph of temperament so as to show its daily fluctuations: grave and gay, up and down, lamentation and revelry, self-love and self-disgust. You get here all my thoughts and opinions, always irresponsible and often contradictory or mutually exclusive, all my moods and vapours, all the varying reactions to environment of this jelly which is I.”
—W.N.P. Barbellion (1889–1919)