Haming Distance and Chromatic Number

Question

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

Comments

@sourav_anand ans given as 2/5 . it might be wrong also. pls explain your approach
Thx in advance

Answer 1

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

Comments

@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?