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:

★DONATE★

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

Follow Wrath of Math on...

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?

[giatoyama]

Please use this knowledge to solve the kn-44 hypercube blueprint cypher 🙏

[benmack]

Who else is here after the kn-44 hypercube Cypher was discovered? 😂

[oranghue]

I ask of you to assist the COD Zombies community in solving the KN-44 hypercube cypher.

[siddharthasingh]

I am wondering why do we have such a low no of likes for such a fantastic explaination of hypercube graph. I am amazed with how easily it explains it all.

[ScriptureResearchCentre]

Anyone here from Skite innit's video on THE IMPOSSIBLE EASTER EGG FINALLY FOUND! JASON BLUNDELL'S 8 YER SECRET (Black Ops 3 Zombies). I wish one of these mathematicians would look into it.

[anaghgupta]

Really loved how beautifully you described each and everything in the video. Big ups for your content bro!

[callofdutywii]

Help us WrathOfMath you’re our only hope to solve the KN44 cipher

[mounikathogiti]

Really helpful and clearly explained. Thank you!

[monettedyar]

Learned a lot. My instructor's explanation didn't come close to this quality of instruction. Thank you so much!

[mubasshirkhan]

I was struggling in this topic, thank you so much, you really explained it so beautifully... 👍

[brandonn]

“You know how long I’ve been waiting for this…”

[godingly]

Thank you very much, very helpful. I'm interested in what software / app you use for writing, it looks great.

[priyanshinahar]

Thank you so much for the amazing video ❤️
Love from India 🇮🇳

[adriasorensen]

2^0 =1 which could stand for the number of points in a dimension. For example 2^0=1, so 0 is the dimension and 1 is the point in the zeroth dimension. Then, 2^1=2 which would be the 1st dimension that has 2 points on a line. 2^2=4 which equals the 4 points on a 2D square for the second dimension. 2^3=8 which would be the 8 points on a 3d cube in the third dimension. 2^4 = 16 which would be the 16 vertices on a 4 dimensional cube or tesseract....then, a 5d cube has 32 vertices (2^5=32). etc
You can also connect binary points, music note lengths, and physics light colors going in opposite directions for the dimensions of a 3d cube to connect them all.

[rahulshah]

Another great video! Can we see more hypercube videos? Good videos on De Bruijn sequence with eulerian tours and proving hypercube proofs with induction are especially hard to find ;)

[zafer]

Very nice drawing, thanks for your time!

[zoasis]

Thanks for this!
Question: How do we prove sum(deg-(v)) = sum(deg+(v)) = |E| for directed graphs?

[ethanhunt]

can you explain crossing number of Hypercube as well

[taniadevi]

thanks it was really very much helpful

[НикитаПупкин-хщ]

Hi !
I have a question to the definition of the Hypercube . Do you know how you can formally and cleanly define Q(n) = (Vn, En)??Because we have some task at the school, where we define it as reсursively, like<
For n e N, the hypercube Qn is defined as follows:
1) Q(0) is a single vertex ( 1 point )
2) Qn+1 is obtained by taking two disjoint copies of Qn and linking each vertex in one copy of Qn to the corresponding vertex in the other copy of Qn.
*We could also obtain Qn by labeling 2^n vertices with distinct n-bit binary strings, and by connecting those vertices by edges whose strings differ in exactly one bit >
And they want have for this 2 version formal and cleanly definition... If you have some idea what does it mean, I'll be very grateful to you ((: