GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
421 views
What is the minimum number of colors needed to color a graph with five vertices. The graph contain a cycle also
asked in Graph Theory by Veteran (10.9k points)   | 421 views

4 Answers

+5 votes
Best answer

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

graph coloring

answered by Boss (9.4k points)  
selected by
Works only if the 5th vertex is disconnected. For graph coloring I guess connection is implied.

if it a null graph then only 1 colour is needed .

Bad miss. You are correct :)

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 .

 

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 .

+1 vote
if there is cycle of 4 verticces then 2 colour required if there is cycle of 5 vertices then 3 colors are required
answered by Active (1.2k points)  
+1 vote
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.
answered by Boss (7.3k points)  
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
–2 votes
its 3. draw a graph and colour it and check
answered by (189 points)  
Minimum should be 2. (They are saying graph has a cycle , not that graph is cycle !)


Top Users Mar 2017
  1. rude

    4018 Points

  2. sh!va

    2994 Points

  3. Rahul Jain25

    2804 Points

  4. Kapil

    2608 Points

  5. Debashish Deka

    2104 Points

  6. 2018

    1414 Points

  7. Vignesh Sekar

    1336 Points

  8. Bikram

    1218 Points

  9. Akriti sood

    1186 Points

  10. Sanjay Sharma

    1016 Points

Monthly Topper: Rs. 500 gift card

21,445 questions
26,757 answers
60,936 comments
22,954 users