The Gateway to Computer Science Excellence
0 votes

How to solve it(clear explanation please)

in Graph Theory by Junior (631 points) | 108 views
88 ? Whats the ans given.

I have doubt, how n vertices are representing all $2^n$ strings of length n.
Yes I too think 88 will be answer
answer = 88
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.

2 Answers

+1 vote
Best answer
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 by
Proper Explanation for this question.

Thank you, sir

for share valuable and proper solution.
0 votes

the solution provided by Made Easy, 

by Junior (631 points)
The formula for this question.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,385 answers
105,343 users