GATE IT 2006 | Question: 25

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. $\frac{1}{\left(2^{n-1}\right)}$
• B. $\left(\frac{1}{n}\right)$
• C. $\left(\frac{2}{n}\right)$
• D. $\left(\frac{3}{n}\right)$

Comments

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

---

@set2018,

For the diameter, the bit difference (Hamming distance) between the two nodes should be maximum.

For example: For n = 3,  000  $\rightarrow$ 001  $\rightarrow$  011  $\rightarrow$ 111.

---

set2018 $diameter = max(eccentricity(v), v \  \epsilon \ G)$

Answer 1

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 $\left(n-1\right)$ edges or $'n'$ vertices to get a path b/w two arbitrary points.

So ratio is $\left(\frac{2}{n}\right).$

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

Comments

for traversing from 000. . .0   ⟶  111. . .1   , we require to traverse atleast 'n' edges.

---

How to find diameyer of the graph ?

---

Diameter is shortest path of maximum lenght  in between any two vertices of a graph. maximum lenght can occure between any two vertices. for this we can do it by intution or by applying all pair shotest path algorithm(floyed warshall)

---

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.

---

Plz explain it through diagram or some derivative solution????? M confused

---

Link to the MIT page in answer: http://web.archive.org/web/20100715032114/https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2005/assignments/pset5_soln.pdf

---

How to draw K-map here? Can You show it please...

---

https://math.stackexchange.com/questions/301562/prove-n-cube-is-bipartite

---

How did we conclude this is BIPARTITE ??    How to coclude if ANY graph is bipartitte ??

---

People who are wondering why the resultant K-map will be bipartite, here's how. 

 

---

Every 2-chromatic graph is known to be bipartite. Converse holds except a particular case - every bipartite graph except graphs of 2 or more isolated nodes (no edges whatsoever) is 2-chromatic.

---

Pritish,

Are there bipartite graphs with more than  two isolated vertices?

---

https://math.stackexchange.com/questions/1503130/can-bipartite-graphs-have-isolated-vertices

---

toxic desire,

according to your diagram the diameter would be 4 not 3 you missed the edge between 

1. 000 and 010 [one bit change ]
2. 100 and 110 [one bit change ]  if you make these edges then the diameter will be 3 so ans 2/3

---

For example let’s take a 3-bit string  
then 000→ 001 → 011→ 111 we would require 3 edges
So in general diameter will be n ,not (n-1)
correct me If i am wrong

Answer 2

Eccentricity is we have to traverse max distance using optimal path (i.e by using min vetrices)

Max. Eccentricity (i.e Diameter) here is 3, as we can start from any vertex say (000) and to reach vertex (111) diameter is 3.

Hence, the ratio 2/n.

n is here 3 i.e length of bit string

 

Answer 3

Answer better explained here :https://gateoverflow.in/38185/haming-distance-and-chromatic-number

Answer 4

(ans c)

It can be easily solved by putting the value of n=1.

I.e, we have to node '0' and '1'. And they are connected with an edge. Here C.N. is 2 and diameter is 1. So ratio is 2.

Now put n=1 in option and check whether answer is 2 or not.

Comments

@Ritik Jain RJ What an idea sirji 😅🙏