4 votes 4 votes What is the minimum number of colors needed to color a graph with five vertices. The graph contain a cycle also Graph Theory graph-theory graph-coloring + – Sankaranarayanan P.N asked Jun 25, 2015 Sankaranarayanan P.N 3.0k views answer comment Share Follow See 1 comment See all 1 1 comment reply smsubham commented Dec 19, 2017 reply Follow Share 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. 0 votes 0 votes Please log in or register to add a comment.
Best answer 9 votes 9 votes 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 Pranay Datta 1 answered Jun 25, 2015 • selected Dec 3, 2015 by Akash Kanase Pranay Datta 1 comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Arjun commented Jul 28, 2015 reply Follow Share Bad miss. You are correct :) 1 votes 1 votes worst_engineer commented Aug 21, 2015 reply Follow Share Hi @Pranay Datta 1 @Arjun sir Can you please explain this logic ? Because I knew C5 or any odd vertices cycle graph is 3 colorable. As , it already contains a cycle . 1 votes 1 votes Pranay Datta 1 commented Aug 22, 2015 reply Follow Share 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 . 4 votes 4 votes Please log in or register to add a comment.
1 votes 1 votes if there is cycle of 4 verticces then 2 colour required if there is cycle of 5 vertices then 3 colors are required akash answered Jul 26, 2015 akash comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes 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. Anurag_s answered Jul 28, 2015 Anurag_s comment Share Follow See all 4 Comments See all 4 4 Comments reply Pranay Datta 1 commented Jul 28, 2015 reply Follow Share 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) . 0 votes 0 votes Anurag_s commented Jul 28, 2015 reply Follow Share 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 1 votes 1 votes Pranay Datta 1 commented Jul 28, 2015 reply Follow Share yes you are right , they says for a cycle but the best case for this 2 which is minimum . 0 votes 0 votes Anurag_s commented Jul 28, 2015 reply Follow Share Still a bit confused should we consider best case here or worst case 0 votes 0 votes Please log in or register to add a comment.
–2 votes –2 votes its 3. draw a graph and colour it and check Hai Hai answered Jul 7, 2015 Hai Hai comment Share Follow See 1 comment See all 1 1 comment reply Akash Kanase commented Dec 3, 2015 reply Follow Share Minimum should be 2. (They are saying graph has a cycle , not that graph is cycle !) 2 votes 2 votes Please log in or register to add a comment.