Intro to Hypercube Graphs (n-cube or k-cube graphs) | Graph Theory, Hypercube Graph

What are hypercube graphs? Sometimes called n-cube or k-cube graphs, these graphs are very interesting! We’ll define hypercube graphs/k-cube graphs in today’s graph theory video lesson. We’ll also go over how to somewhat easily construct hypercube graphs, and some of their interesting properties! #graphtheory #hypercube

Join Wrath of Math to get exclusive videos, lecture notes, and more:
   / @wrathofmath  

Graph Theory course:    • Graph Theory  
Graph Theory exercises:    • Graph Theory Exercises  

★DONATE★
◆ Support Wrath of Math on Patreon:   / wrathofmathlessons  
◆ Donate on PayPal: https://www.paypal.me/wrathofmath

Outro music by Ben Watts and is available for channel members.

Follow Wrath of Math on...
● Instagram:   / wrathofmathedu  
● TikTok:   / wrathofmathedu  
● X: https://x.com/wrathofmathedu
● Facebook:   / wrathofmath  

Hypercube graphs are usually denoted Qn. The graph Qn has 2^n vertices. To construct the edges, we label the vertices 0 to 2^n - 1 in binary. Binary is the base 2 number system. A binary digit is called a bit, so to construct the edges we just join every pair of vertices that differ by exactly one bit. It sounds easy, and it is pretty easy, but it can get messy quickly!

Another easy way to construct these k-cube graphs is to make 2 copies of the k-1 cube graph. So to make Q4 we would make two copies of Q3. Then, add leading 0s to the labels of the vertices in one copy, and add leading 1s to the vertex labels in the other copy. Then create the necessary edges joining vertices that differ by exactly one bit. It’s actually kind of fun!

Hypercube graphs are so named because they are graph theory versions of cubes in different dimensions. They are bipartite, and the Qn graph is n-regular, meaning all of its vertices have degree n. Can you figure out why these things are true?