I'm currently not really able to come up with a proof for this particular problem.
Let $G=(V,E)$ be a graph with the property that $∀ v ∈ V$, $χ(G−v) = χ(G)−1$. Show that $G$ is connected.
In other words: If you delete any vertex of the graph, the chromatic number will be reduced by one.
From my understanding this can only be the case in a complete graph. Since all vertices of a complete graph are connected with each other the chromatic number must be reduced by one if you delete any vertex. Which means that if I'm able to show that $G$ is a complete graph, I will have automatically proven that $G$ is connected since every complete graph is connected. I'm just not sure how to prove that $G$ is a complete graph or how to tackle this problem in general. I'm very thankful for any help I can get!
Best Answer
Suppose $G$ is disconnected. The chromatic number of such a graph is the maximum of the chromatic numbers of its components, but a vertex can only belong to one component. Thus, if the removal of any particular vertex lowers the overall chromatic number, the component that vertex belongs to must have strictly higher chromatic number than that of the other components.
Repeating this argument, subjecting the remaining components to vertex removal, yields that every component's chromatic number is strictly higher than the others', which is absurd. Therefore, $G$ is connected.