graph coloring

Question

What is the minimum number of colors needed to color a graph with five vertices. The graph contain a cycle also

Comments

Minimum required is 2. (Check Selected Answer for example)

Maximum required is 4 for a graph has a triangle and both of the other 2 vertices connected to one vertex in a triangle.

Answer 1

If you say minimum then it should be 2 ( a cyclic graph with even  vertices required 2 colours and for odd 3 ) and we can form a cyclic graph with 4 vertices and 5th vertex will connect any one of that cyclic vertices with one edge (of course :D ) . peace

Comments

Bad miss. You are correct :)

---

Hi @Pranay Datta 1

@Arjun sir

Can you please explain this logic ? Because I knew C₅ or any odd vertices cycle graph is 3 colorable. As , it already contains a cycle .

---

the question says "The graph contain a cycle " 

it didnot mention any odd or even length cycle .

so if we take even length then it wiil be 2 .

Answer 2

if there is cycle of 4 verticces then 2 colour required if there is cycle of 5 vertices then 3 colors are required

Answer 3

If Graph contains cycle,either its odd cycle or even cycle

case 1:odd cycle :3

case 2:even cycle :2

we should take best solution in worst case so it will be 3 colors.

Comments

the minimum no. of colour need with 5 vertices which  contains a cycle is 2 . and in wrost case with 5 vertices we need 5 colours (k5) .

---

K5 has nany cycles here he said a cycle ie 1 cycle.. 

And we have to give minimum color in  worst case.. Even will be the best case

---

yes you are right , they says for a cycle but the best case for this 2 which is minimum .

---

Still a bit confused should we consider best case here or worst case

Answer 4

its 3. draw a graph and colour it and check

Comments

Minimum should be 2. (They are saying graph has a cycle , not that graph is cycle !)