Consider the undirected graph G defined as follows. The vertices of G are bit strings of length n. We have an edge betwe...

Question

Consider the undirected graph G defined as 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/(n-1)
B. 1/n
C. 2/n
D. 2/(n+1)

Accepted Answer

C. 2/n The graph described is the n-dimensional hypercube Q_n: vertices are all n-bit binary strings and edges connect strings differing in exactly one bit. Q_n is bipartite (partition by parity of number of 1-bits), so it needs exactly 2 colours. The diameter is n, since you need at most n single-bit flips to reach any vertex from any other. Therefore the ratio is 2/n.