3 This question concerns the simple graph depicted at right (a) Three colours, R

Question

3 This question concerns the simple graph depicted at right (a) Three colours, Red, Green and Blue, are available for vertex-colouring Standard convention: adjacent vertices must have different colours.) How many different colourings are there? Justify your answer by providing dia- grams showing each of the colourings. (Use coloured pens or pencils.) [2 marks] (b) Calculate the chromatic polynomial for the graph, showing all working. Where possible you may use combinatorial counting on intermediate graphs rather than the decomposition theorem. E.g: k-1 k-2 for HK-4, prr(k)-k(k-1)2(4-1)2 by virtue of the count k k-1 [4 marks] k-2

Explanation / Answer

Start with the inner one which can be filled in -> 3*2*1 =6 ways( let u,v,w be the vertices of inner triangle. If u is colured red, v and w must be colured with green and blue or blue and green respectively.Hence allocating a single colour to u brings two choices and u can be coloured with three different colours hence total no. of ways in innermost triangle can be coloured is 3*2*1=6ways

Then the outermost can be filled in -> 2*1*1 = 2 ways( In a similar way)

Hence , Total number of ways to fill this figure-> 6*2= 12ways

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.