Given an irregular graph $G$, show $\chi(G) \leq \triangle(G)$

164 Views Asked by At

We know that by Brooks theorem, if the graph is not a complete graph and does not contain an odd cycle then $\chi(G) \leq \triangle(G)$. My guess is an irregular graph mean a graph not all of its vertices have the same degree. But then a triangle attached to a path is irregular and doesn't work. I got this problem from here: enter image description here

1

There are 1 best solutions below

2
On BEST ANSWER

Well, you also need the graph $G$ to be connected, lest you take one component of $G$ to be $K_{d+1}$ and another component of $G$ a graph of maximum degree $d$ (but not all vertices degree $d$).

To do Exercise 2.4, use induction. Precisely, we are proving that a connected graph $G$ with maximum degree $d$ and with at least one vertex of degree less than $d$, can be $d$ coloured, which will establish Exercise 2.4. To this end: Remove a vertex $v$ of degree strictly less than $d$. Then as $G$ is connected each component of the graph $G \setminus \{v\}$ has a vertex $u$ of degree strictly less than $d$ [indeed, each of $v$'s neighbours in $G$ have dgree strictly less than $d$ and $v$ has a neighbour in each component of $G \setminus \{v\}$]. So by the inductive hypthesis $G \setminus \{v\}$ can be properly colored with $d$ colors. But as $v$ has degree strictly less than $d$, that leaves at least one color to color $v$ to extend this coloring to a propert coloring of $G$ with only $d$ colors.