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

4 Answers

+6 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.5k 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.4k 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 May 2017
  1. akash.dinkar12

    3578 Points

  2. pawan kumarln

    2314 Points

  3. Bikram

    1950 Points

  4. Arjun

    1852 Points

  5. sh!va

    1682 Points

  6. Debashish Deka

    1296 Points

  7. Devshree Dubey

    1282 Points

  8. Arunav Khare

    1122 Points

  9. Angkit

    1072 Points

  10. LeenSharma

    1028 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 29 - Jun 04
  1. Arunav Khare

    246 Points

  2. Arjun

    202 Points

  3. pawan kumarln

    108 Points

  4. Rupendra Choudhary

    94 Points

  5. Niharika 1

    90 Points


22,909 questions
29,243 answers
65,403 comments
27,745 users