The Gateway to Computer Science Excellence
+15 votes
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 :
closed as a duplicate of: GATE2006-IT-25
in Graph Theory by Boss (21.5k points)
retagged by | 1.2k views
@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


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.2k points)
edited by

n=3 bits


Diameter how can be 5????. It should be 3...
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]
@sourav_anad how did u visualize it as cube ?

According to ur picture for 3 bit length
would the ratio be 2/3 ?
yes...for n= 3 bit ratio =2/3 and for n=5 bit ratio=2/5;
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?
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,342 answers
105,215 users