Question

 The number of colors needed to edge color a simple graph with maximum degree Δ is?

Is this there in portion?

Answer 1

edge colouring can be anything between maximum degree or maximum degree -1 depending on the instance of the graph/.

Comments

Why maximum degree -1 ? Shouldn't the minimum number of colors required be maximum degree since all the edges protruding from the vertex with max. degree should be different?

---

This answer is incorrect. Please edit it. The correct answer is maximum degree or maximum degree+1.
See here https://en.wikipedia.org/wiki/Edge_coloring

Answer 2

https://en.wikipedia.org/wiki/Vizing%27s_theorem

Answer 3

Hi I would like to explain this :)

This question is related to Graph Colouring . In Graph colouring , No adjacent nodes ( 2 nodes connected by a edges ) must not have some colour . So here if they say when a degree of a node ( say A ) is n , it mean A is attached to n nodes by an edges .

Say if a degree of a node B is 3 then it is adjacent to node D E F ( D E f may or may not be adjacent . But that is not our concern for now ) by an edge connecting them . So we know that no 2 adjacent nodes will have single colour .

so if i give node b =red colour Node D = blue colur node E = balck Node F = purple So if you see for since node b  has degree 3 . To do proper graph colouring technique , we need have 4 colours so that no adjacent nodes have same colour .

So by stating above example I can conclude that in general if a node has a degree n , then it adajcent to n nodes . And so for a proper graph colouring you need to colour with n+1 colours .

I hope it help you :)