enter image description here

Also, what is the meaning of the notation used in the question- c: v->{0,1,2....k-1} such that c(u)!=c(v)?

  • $\begingroup$ Do you have any further information about the graph? Because the informations given are not sufficient to decide which of the options is not correct? $\endgroup$ – Pepsilon7 Sep 24 at 9:54
  • 1
    $\begingroup$ $c:v\rightarrow\{0,1,2,\dots,k-1\}$ such that $c(u)!=c(v)$ for every edge $(u,v)$ means that it is impossible for to vertices wich are connected by an edge to have the same color. $\endgroup$ – Pepsilon7 Sep 24 at 9:56
  • $\begingroup$ @Pepsilon7 No further information was provided in the question. It was asked in an examination and according to the answer key the correct option is 3 (i.e., G has cycles of odd length). $\endgroup$ – Parveez Ahmed Sep 24 at 10:11
  • $\begingroup$ @Pepsilon7 I think according to the question the number of vertices should be equal to the number of colors, right? For example, if I consider a complete graph with 4 vertices, then the number of colors(chromatic number) that I get is 4(equal to number of vertices) and there are cycles of both even and odd length(length 3 and 4) there. Please correct me if I am wrong. $\endgroup$ – Parveez Ahmed Sep 24 at 10:20
  • $\begingroup$ Oh I see how the question is ment. Assuming that all the other options are true the third option is in fact wrong. I can provid the proof if desired. $\endgroup$ – Pepsilon7 Sep 24 at 10:22

Proof that a graph is bipartite if and only if the graph does not contain any cycles of odd length:

So for the $\Leftrightarrow$ relation to be true you have to show both directions:

If your graph contains a cycle of odd length you can show by counter example that this graph can not be colored with 2 colors such that two neighbour vertices do not have the same color. E.g take a cycle with 5 vertices. You can see that you need at least 3 colors to coler this graph.

So for this direction you have a graph wich does not contain a cycle of odd length. To show that this graph can be colored with only two colors you can start a breadth-first search from an arbitrary vertex $s$. Whenever a vertex $v$ gets visited by the breath-first search it gets colored with color 1 if its distance from $s$ denoted $d(v)$ is even, respectively gets colored with color 2 if its distance $d(v)$ is odd.
Since the graph does not contain any cycle of odd length there can not be an edge which neighbouring vertices get the same color.

This proof shows that if the options 1 and 2 of your questions are true, the option 3 has to be false. And since the option 4 is the opposite of the third option it is also true.

$c:v\rightarrow\{0,1,2,\dots,k-1\}$ such that $c(u)\not=c(v)$ for every edge $(u,v)$ simply means that two adjacent vertices can not be colored with the same color.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.