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
After reading this question words "Gray code", "Hypercube graph", "Haming Distance" and "Even length cycles" are coming in mind.
Now if you are thinking why Hypercube graph has chromatic no = 2 or Even length cycle then refer -->
https://math.stackexchange.com/questions/227681/how-to-find-chromatic-number-of-the-hypercube-q-n
Chromatic number is 2 so maximum independent set size is $2^{n-1}$.
how u calculate diameter of graph?
The diameter of a graph is the length of the shortest path between the most distanced nodes
Answer is (C)
For the given condition we can simply design a K-MAP and mark an edge between every two adjacent cells in K-Map.(adjacency has to seen just as we do for minimization )
That will give us a Bipartite graph. chromatic number for this =2
Also from the same we can conclude that we need ,for a 'n' bit string, to traverse NO MORE than (n-1) edges or 'n' vertices to get a path b/w two arbitrary points.
So ratio is 2/n.
The given graph is actually hypercubegraph.
https://en.wikipedia.org/wiki/Hypercube_graph
See problem 4 here: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2005/assignments/pset5_soln.pdf
for traversing from 000. . .0 ⟶ 111. . .1 , we require to traverse atleast 'n' edges.
To find the diameter of a graph, first find the shortest path between each pair of vertices. The greatest length of any of these paths is the diameter of the graph.
Gatecse
OK @
In d link mentioned below. Yeah. :)