+15 votes
1.1k views
Consider the undirected graph G defined as follows. The vertices are bit string of length 5. We have an edge between vertex “a” and vertex “b” iff “a” and “b” differ only in one bit possible (i.e., hamming distance1). What is the ratio of chromatic number of G to the diameter of G?

Model Question : https://gateoverflow.in/3564/gate2006-it_25
closed as a duplicate of: GATE2006-IT-25

retagged | 1.1k views
0
@sourav_anand ans given as 2/5 . it might be wrong also. pls explain your approach
Thx in advance

## 1 Answer

+29 votes
Best answer
apply the given condition of connectivity to 2 bits..00==>01==>11==>10==>00

for 3 bits..image in comment box

ACTUALLY IT IS  A N CUBE...

vertex of n cube=n;

degree of n cube=n;

edges of n cube=n*2^(n-1)
chromatic number=2(ALWAYS)
hence chromatic number of the graph=2

now diameter of graph=number of bits =5

thus ratio =2/5
by Boss (16.1k points)
edited by
+6

n=3 bits

0
http://mathworld.wolfram.com/GraphDiameter.html

Diameter how can be 5????. It should be 3...
0
obviously diameter will be three but here n= 3 bits and i have written it 5 for n=5..u make the graph of 5 bits u will get [email protected]
+1
@sourav_anad how did u visualize it as cube ?

According to ur picture for 3 bit length
would the ratio be 2/3 ?
+5
yes...for n= 3 bit ratio =2/3 and for n=5 bit ratio=2/5;
0
For n=2, the ratio is coming as 2/n as for 2 bits hamming distance is not equal to 2.

What would be answer for n=2?

+1 vote
1 answer
1
+2 votes
0 answers
2
0 votes
1 answer
3
0 votes
1 answer
4