Consider the undirected graph G defined as follows. The vertices of G are bit…
2006
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/(2n-a)
- B.
1/n
- C.
2/n
- D.
3/n
Attempted by 99 students.
Show answer & explanation
Correct answer: C
Key facts: The graph is the n-dimensional hypercube: vertices are bit strings of length n, and edges join strings that differ in exactly one bit.
Chromatic number = 2. Partition vertices by the parity of the number of 1s (even vs odd). Adjacent vertices have opposite parity, so two colors suffice. For n >= 1 at least two colors are necessary, so the chromatic number is 2.
Diameter = n. The distance between two vertices is their Hamming distance (the number of differing bits). The maximum possible Hamming distance between two n-bit strings is n (e.g., a string and its bitwise complement), so the graph diameter is n.
Therefore the ratio of the chromatic number to the diameter is 2/n. (This is for n >= 1; for n = 0 the graph has one vertex and diameter 0, which makes the ratio undefined.)