713 views
0 votes
0 votes

Can anyone explain how this is to be solved?

2 Answers

Best answer
1 votes
1 votes
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
selected by
1 votes
1 votes
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

Related questions

0 votes
0 votes
0 answers
1
Chaitrasj asked Jan 14, 2019
609 views
0 votes
0 votes
0 answers
2
jatin khachane 1 asked Jan 13, 2019
785 views
0 votes
0 votes
0 answers
3
Gate Fever asked Jan 13, 2019
721 views
consider the following languages M and NM={W$W^{R}$W$W^{R}$ | W$\epsilon$(0,1)*}N={W1$W1^{R}$W2$W2^{R}$ | W1,W2$\epsilon$(0,1)*which of the following languages are CFL?
0 votes
0 votes
1 answer
4