Consider an n dimensional cube and it’s complement graph represented by G and…
Consider an n dimensional cube and it’s complement graph represented by G and H respectively. y×210 edges are present in graph H if n=11. Find the value of y?_________
Answer: 2036 — Key facts: For an n-dimensional cube, the number of vertices is 2^n and each vertex has degree n. Set n = 11, so the number of vertices V = 2^11. Number of…
Attempted by 37 students.
Show answer & explanation
Correct answer: 2036
Key facts: For an n-dimensional cube, the number of vertices is 2^n and each vertex has degree n.
Set n = 11, so the number of vertices V = 2^11.
Number of edges in the cube graph G: by the handshake theorem E_G = (V * degree)/2 = (2^11 * 11)/2 = 11 * 2^10.
Total possible edges in a complete graph on V vertices: E_complete = V(V - 1)/2 = 2^11(2^11 - 1)/2 = (2^11 - 1) * 2^10.
Edges in the complement graph H: E_H = E_complete - E_G = [(2^11 - 1) - 11] * 2^10 = (2047 - 11) * 2^10 = 2036 * 2^10.
Therefore, y = 2036.