Discrete

Question

What is the upper bound for the Chromatic Number given by Brooks' theorem for the Petersen graph?

 (a) 2

 (b) 3

 (c) 4

 (d) None of the above

Answer 1

${\color{Red}B\color{Red}R \color{Red}O\color{Red}O\color{Red}K \,\,\text{THEOREM -:}}$-:$\text{Chromatic Number of anyCONNECTED graph having all its vertex atmost degree }\Delta \text{can be no greater than} \Delta \text{except complete graph and cycle graph}$

---

Petersen_graph  is not a complete graph .It is connected and every vertex atmost $3$ degree so , according to Brook theorem ,

chromatic number of petersen graph=$3$