2,971 views
4 votes
4 votes
What is the minimum number of colors needed to color a graph with five vertices. The graph contain a cycle also

4 Answers

Best answer
9 votes
9 votes

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

selected by
1 votes
1 votes
if there is cycle of 4 verticces then 2 colour required if there is cycle of 5 vertices then 3 colors are required
1 votes
1 votes
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.
–2 votes
–2 votes
its 3. draw a graph and colour it and check

Related questions

0 votes
0 votes
1 answer
1
Sahil_Lather asked Apr 15, 2023
439 views
Graph G is obtained by adding vertex s to $K_{3,4}$ and making s adjacent to every vertex of $K_{3,4}$ .The find the minimum number of colours required ot edge-colour is ...
4 votes
4 votes
2 answers
2
Balaji Jegan asked Nov 27, 2018
2,486 views
How many ways are there to color this graph from any $4$ of the following colors : Violet, Indigo, Blue, Green, Yellow, Orange and Red ?There is a condition that adjacent...
3 votes
3 votes
1 answer
3
0 votes
0 votes
0 answers
4
dan31 asked Nov 6, 2018
1,197 views
If G is a connected k-regular graph with chromatic number k+1, then find the number of edges in G?