The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+3 votes
732 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.7k points) | 732 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 (10k 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 (8.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 (199 points)
Minimum should be 2. (They are saying graph has a cycle , not that graph is cycle !)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

28,831 questions
36,676 answers
90,578 comments
34,638 users