GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
371 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.7k points)   | 371 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.2k 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 Jan 2017
  1. Debashish Deka

    8126 Points

  2. sudsho

    5042 Points

  3. Habibkhan

    4706 Points

  4. Vijay Thakur

    4458 Points

  5. Bikram

    4348 Points

  6. saurabh rai

    4212 Points

  7. Arjun

    4010 Points

  8. santhoshdevulapally

    3722 Points

  9. GateSet

    3292 Points

  10. Sushant Gokhale

    3286 Points

Monthly Topper: Rs. 500 gift card

19,122 questions
24,034 answers
52,724 comments
20,276 users