GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
616 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 (11.2k points)   | 616 views

4 Answers

+7 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.7k 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 (8k 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 (199 points)  
Minimum should be 2. (They are saying graph has a cycle , not that graph is cycle !)


Top Users Sep 2017
  1. Habibkhan

    6970 Points

  2. Warrior

    2490 Points

  3. Arjun

    2368 Points

  4. rishu_darkshadow

    2136 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. makhdoom ghaya

    1760 Points

  8. manu00x

    1750 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,060 questions
33,668 answers
79,747 comments
31,079 users