Question 148
a. If a single vertex (and all its incident edges) is removed from a finite graph, show that the graph's chromatic number cannot decrease by more than 1.
b. Show that, for any $n\gt 2$, there are infinitely many graphs with chromatic number $n$ such that removing any vertex (and all its incident edges) from the graph decreases its chromatic number.
b. Show that, for any $n\gt 2$, there are infinitely many graphs with chromatic number $n$ such that removing any vertex (and all its incident edges) from the graph decreases its chromatic number.