Lesson plan

Hypercube graph

{{Infobox graph | name = Hypercube graph | image = Hypercubestar.svg | image_size = 200px | image_caption = The hypercube graph Q_4 | vertices = 2^n | edges = 2^{n-1}n | automorphisms = n!2^n | chromatic_number = 2 | chromatic_index = | girth = 4 if n\ge 2 | diameter = n | spectrum = \{(n - 2 k)^{\binom{n}{k}}; k = 0, \ldots, n\} | properties = Symmetric Distance regular Unit distance Hamiltonian Bipartite Polytopal | notation = Q_n }} In graph theory, the hypercube graph Q_n is the edge graph of the n -dimensional hypercube, that is, it is the graph formed from the vertices and edges of the hypercube. For instance, the cube graph Q_3 is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. Q_n has 2^n vertices, 2^{n-1}n edges, and is a regular graph with n edges touching each vertex. The hypercube graph Q_n may also be constructed by creating a vertex for each subset of an n -element set, with two vertices adjacent when their subsets differ in a single element, or by creating a vertex for each n -digit binary number, with two vertices adjacent when their binary representations differ in a single digit. It is the n -fold Cartesian product of the two-vertex complete graph, and may be decomposed into two copies of Q_{n-1} connected to each other by a perfect matching.…

Back to article

Article summary

{{Infobox graph | name = Hypercube graph | image = Hypercubestar.svg | image_size = 200px | image_caption = The hypercube graph Q_4 | vertices = 2^n | edges = 2^{n-1}n | automorphisms = n!2^n | chromatic_number = 2 | chromatic_index = | girth = 4 if n\ge 2 | diameter = n | spectrum = \{(n - 2 k)^{\binom{n}{k}}; k = 0, \ldots, n\} | properties = Symmetric Distance regular Unit distance Hamiltonian Bipartite Polytopal | notation = Q_n }} In graph theory, the hypercube graph Q_n is the edge graph of the n -dimensional hypercube, that is, it is the graph formed from the vertices and edges of the hypercube. For instance, the cube graph Q_3 is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. Q_n has 2^n vertices, 2^{n-1}n edges, and is a regular graph with n edges touching each vertex. The hypercube graph Q_n may also be constructed by creating a vertex for each subset of an n -element set, with two vertices adjacent when their subsets differ in a single element, or by creating a vertex for each n -digit binary number, with two vertices adjacent when their binary representations differ in a single digit. It is the n -fold Cartesian product of the two-vertex complete graph, and may be decomposed into two copies of Q_{n-1} connected to each other by a perfect matching.…

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.