108 views

How to solve it(clear explanation please)

| 108 views
0
88 ? Whats the ans given.

I have doubt, how n vertices are representing all $2^n$ strings of length n.
0
Yes I too think 88 will be answer
0
0
I got ans by assuming $2^n$ states/nodes. In question they have mentioned n nodes, which is wrong. To represent $2^n$ differnt strings, you ought to have $2^n$ nodes.
0
88

+1 vote
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
by Active (2.7k points)
selected
0
Proper Explanation for this question.

Thank you, sir

for share valuable and proper solution.

the solution provided by Made Easy,

by Junior (631 points)
0
The formula for this question.