ME- CBT1

Question

Can anyone explain how this is to be solved?

Comments

two vertices are adjacent if the bit strings that they represent differ in exactly one bit position.

how are we applying this line in the formula for n cube graph ?

---

let for 3 bits, there are 8 vertices.

those are 000,001,010,011,100,101,110,111

now there should be an edge between 000 and 010 due to they are differ by 1 bit !

But there should be no edge between 001 and 010 due to they are not differ by 1 bit !

---

88

Answer 1

edges in H4 = 4*2^(4-1) = 32   { as no of edges in n cube graph  = n*2^(n-1)}

now , total  no of vertices  in H4   = 2^4 = 16

so , total edges in complete graph with 16 vertices = 16C2  = 120

so no of edges in complement of H4 = 120 - 32 = 88

Answer 2

for n=4 total 2^4=16 bit strings are possible, each bit string represents a vertex.

Now each vertex is connected to 4 other vertices. Why???

for example, vertex 0000 is connected to every other vertex where bit differs in exactly one-bit position so 0000 is connected to 0001, 0010, 0100, 1000

Similarly, each vertex is connected to 4 other vertices so the total number of edges in H4 = (16*4)/2 = 32

Now total number of edges in complete graph = C(16,2) = 120

Number of edges in H4(complement) = 120-32 = 88

Comments

Proper Explanation for this question.

Thank you, sir

for share valuable and proper solution.