We say that a finite, simple, undirected graph $G=(V,E)$ is *vertex-critical* if removing any vertex decreases the chromatic number.


Is there a vertex-critical graph $G=(V,E)$ and $v\neq w\in V$ with $\{v,w\}\notin E$ such that collapsing $v$ and $w$ increases the chromatic number?



Collapsing non-adjacent vertices in vertex-critical graphs
I think this may be a simple unpacking of definitions. I claim there is no such graph.


Let $G$ be vertex-critical. Let $v\neq w \in V$ with $\{v,w\} \not \in E$. Let $k$ be the chromatic number of $G$. Consider $G \setminus v$. Since $G$ is vertex-critical, we can $k-1$-color $G\setminus v$. Do so. Then change this coloring into a $k$-coloring by coloring $w$ a new color, say, ``green.'' Clearly this is still proper since $w$ is the only green vertex. Moreover, since $\{v,w\} \not \in E$, we can extend to a $k$-coloring of $G$ where $v$ is also colored green. But now we have a $k$-coloring of $G$ where $v$ and $w$ are both green- so we can collapse $v$ and $w$ in this coloring and it will be a $k$-coloring of $G/v\sim w$. So collapsing $v$ and $w$ does not increase the chromatic number of $G$.


