Question

An undirected graph G has bit strings of length 100 in its vertices and there is an edge between vertex u and vertex v if and only if u and v differ in exactly one bit position. Determine the ratio of the chromatic number of G to the diameter of G?

(a) 1/2^101

(b) 1/50

(c) 1/100

(d) 1/20

The question was asked during an interview.

The query is from Graphs Properties topic in section Graphs of Discrete Mathematics

Answer 1

Right choice is (b) 1/50

Explanation: For the given condition we can simply design a K-Map and mark an edge between every two adjacent cells in K-map. Hence, that will give us a Bipartite graph and chromatic number for this = 2. Hence the ratio is 2/n=2/100=1/50 and the given graph is actually a hypercube graph.