I was reading about chromatic number from a book by Narsingh Deo.
Where in I spot a theorem which is confusing me.
[ Precisely: theorem 8-3 till brooks extension theorem part]
Here it's given that Brooks showed that if G doesn't have Max Degree+1 vertice complete graph then chromatic number is less than Max Degree. Now I want to ask that what does the author mean by "G doesn't have a complete graph of dmax+1 vertices"
Does the author mean to say , that there has to be either a complete graph (Kn) or a complete graph as subpart of a bigger graph G…?
I know that in a
Complete Graph
and in an
odd cycle graph
We have chromatic number as max degree +1
And in rest of graphs it's less than Max Degree..
Now brooks extended the theorem…from that what I interpret that statement as if any graph has to have it's chromatic number as dmax+1 then it such graphs must have a complete graph present inside them of vertices=dmax+1…which is as good as saying that there has to be only a complete graph…(isn't it..???)
Have a look at this pic.
Now here by the above statement I have drawn a complete graph as a subpart of bigger graph..now in this case the max degree is 5(considering whole graph) so by the statement if I have to get chromatic number as dmax+1 then I need to have a complete graph of dmax+1 vertices in the bigger graph G..so that means I have to have 5+1 =6 vertex complete graph as subpart of bigger graph..which is not possible, in any case…thus it won't have chromatic number dmax+1 and would have less than or equal to dmax…
Best Answer
Brooks' theorem says that any graph of maximum degree $\Delta$ which doesn't contain the complete graph on $\Delta+1$ vertices, or, if $\Delta=2$, an odd cycle, has chromatic number at most $\Delta$.
Now if there is a subgraph which is a complete graph on $\Delta+1$ vertices (or an odd cycle with $\Delta=2$), then every vertex in that subgraph already has $\Delta$ edges within that subgraph, so it can't have any edges to the rest of the graph. So either it is the whole graph, or the graph is disconnected and one of its components is a complete graph with $\Delta+1$ vertices. The other components could have smaller chromatic number, but this component will still force the chromatic number of the whole graph to be $\Delta+1$.