Question

Consider the undirected graph G defined a follows. The vertices of G are bit strings of length n. We have an edge between vertex u and vertex v if and only if u and v differ in exactly one bit position (in other words, v can be obtained from u by flipping a single bit). The ratio of the chromatic number of G to the diameter of G is

• A. $1/\left(2^{n-1}\right)$
• B. 1/n
• C. 2/n
• D. 3/n

Answer 1

The correct option is C 2/n

The hamming distance relation on bit strings has a digraph which will be always an n-cube where n is the number of bits.

Chromatic number of n-cube = 2 (since n-cube is always bipartite). Also the diameter of n-cube = n. So the ratio of chromatic number to diameter of the n-cube = 2/n.