edited by
12,557 views
37 votes
37 votes

The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is

  1. $2$
  2. $3$
  3. $4$
  4. $5$
edited by

7 Answers

Best answer
40 votes
40 votes

$4$ colors are required to color the graph in the prescribed way.

answer = option C

edited by
2 votes
2 votes
note:-The max degree of the vertex is 4 so we need atmost 4 colours to colour the graph

answer is C) 4 only
edited by
0 votes
0 votes

short trick-

first eliminate option here 

according to 4 color theorm we cannot use more than 4 color 

so option (d) is wrong

Now, as you can see it contain cycle with odd n.o of edges i.e 3 

it means it contain atleast 3 colors

so option (a) is wrong

now we can easily check with 3 and 4 colors.

Answer:

Related questions

38 votes
38 votes
4 answers
2
Kathleen asked Sep 18, 2014
8,310 views
The following finite state machine accepts all those binary strings in which the number of $1$’s and $0$’s are respectively: divisible by $3$ and $2$odd and evene...
27 votes
27 votes
5 answers
3
Kathleen asked Sep 18, 2014
18,978 views
Let $A = 1111 1010$ and $B = 0000 1010$ be two $8-bit$ $2’s$ complement numbers. Their product in $2’s$ complement is$1100 0100$$1001 1100$$1010 0101$$1101 0101$