edited by
4,484 views
30 votes
30 votes

How many ways are there to assign colours from range  $\left\{1,2,\ldots,r\right\}$ to vertices of the following graph so that adjacent vertices receive distinct colours?

  1. $r^{4}$
  2. $r^{4} - 4r^{3}$
  3. $r^{4}-5r^{3}+8r^{2}-4r$
  4. $r^{4}-4r^{3}+9r^{2}-3r$
  5. $r^{4}-5r^{3}+10r^{2}-15r$
edited by

6 Answers

30 votes
30 votes

The graph can be colored using minimum $3$ colors and maximum $4$ colors.

No. of ways using $3$ colors $= r(r-1)(r-2).$

No. of ways using $4$ colors $= r(r-1)(r-2)(r-3).$

Total no. of ways $= r(r-1)(r-2) + r(r-1)(r-2)(r-3)$

                               $ =r^4 - 5r^3 + 8r^2 - 4r$

OPTION (C)

edited by
12 votes
12 votes

There can be only two cases when the given condition (adjacent vertices receive distinct colours) will satisfy:

Case 1: All vertices having different colors. Basically in this Case we need four different colors.

Number of ways to do that is -----> r(r-1)(r-2)(r-3)

Case 2: vertex b and d having same color, but other vertices(a and c) having different colors  than b/d and also colors of a and c are different. So, basically in this Case we need three different colors(one color for a, another different color for c and another different color for b/d) .  Number of ways to do that is -----> r(r-1)(r-2)

So in total (Case 1 +Case 2)   Number of ways  are  ---> r(r-1)(r-2)(r-3) + r(r-1)(r-2) = r(r-1)(r-2) [(r-3) +1] = r(r-1) (r-2)^2

= (r^2 -r) (r^2 -4r + 4) = r^4−5r^3+8r^2−4r

Another Simple way of thinking:

Since a,d,c vertices form a triangle(hence adjacent to each other) so, they have to be colored using there different colors.

So, a,d,c vertices can be colored in r * (r-1)* (r-2) ways. Now for b vertex we are left with r-2 choices (because b vertex can't be colored same as vertex a or c). So, a,d,c,b vertices can be colored in r * (r-1)* (r-2) * (r-2) ways such that no adjacent vertices gets same color.  r * (r-1)* (r-2) * (r-2)= r^4−5r^3+8r^2−4r 

 

 

 

 

edited by
2 votes
2 votes

The given question is asking for the chromatic polynomial associated with the given graph.

The following properties of chromatic polynomial might help to eliminate options and save time in the exam for these type of questions.

Let, $P(G,r)$ is a chromatic polynomial associated with a connected graph $G$ which has $n$ number of vertices and $|E|$ number of edges, Then

$1)$ Degree of $P(G,r) = n.$  

$2)$ Coefficient of $r^n$ is $1$.

$3)$ Coefficient of $r^{n-1}$ is $-|E|$

$4)$ Coefficient of $r^{n-2}$ is $\binom{|E|}{2}\;-$ number of triangles in $G.$

$5)$ There is no constant term in a chromatic polynomial $P(G,r).$

$6)$ The signs on the coefficients of the chromatic polynomial are alternate.

$7)$ Sum of the coefficients of a chromatic polynomial is zero.

There are other properties too but these are the simple ones and can be remembered.

Now, for the given question,

Except option $(C),$ all other options are eliminated by property $(7).$

Hence, Answer: (C)

0 votes
0 votes

For nodes a, b and c, we need 3 colors out of r colors, and moreover we can arrange them in any order. So rP3.

And now we need to place a valid color at vertex d. Vertex d have (r - 2) choices(because 2 colors out of r are being utilised by vertices a and c).

So, we have a total of rp3 * (r - 2) ways, which is equivalent to r*(r - 1)*(r - 2)*(r - 2).

Answer:

Related questions