TIFR CSE 2018 | Part A | Question: 9

Question

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?

• A. $r^{4}$
• B. $r^{4} - 4r^{3}$
• C. $r^{4}-5r^{3}+8r^{2}-4r$
• D. $r^{4}-4r^{3}+9r^{2}-3r$
• E. $r^{4}-5r^{3}+10r^{2}-15r$

Comments

c is answer

with r= 3 only c is satisfy:

3*2 = 6

---

We can solve this question with basic understanding.  For 'a' we have 'r'colors , for 'c' we have 'r-1' colors and for 'd' we also have 'r-2' color and for 'b' we have 'r-2' colors... Now multiply all of them this will give answer option C

Answer 1

we can take r=4 

Here there is an odd cycle so 3 colorable

for this odd cycle we can select colors in $^4C_3$ ways

Now considering the arrangement between the colors we get $^4C_3 \times 3! = 24$

Now, 1 vertex remains which can be colored with all the colors except the colors of the adjacent vertices i.e., $^2C_1 = 2$ ways

so total ways of coloring = $24 \times 2 = 48$

If we put value as 4 only option c matches

so answer is (C)

Answer 2

this may help,

 

put r value in each option, the only c is satisfied.