No, there does not exist such a graph. Let $vw$ be a non-edge of $G$ such that collapsing $vw$ increases the chromatic number. This means that for every $\chi(G)$-colouring of $G$, $v$ and $w$ must be coloured differently. Equivalently, $\chi(G + uv)=\chi(G)+1$, so condition (2) is not satisfied.
Tony Huynh
- 32.1k
- 11
- 112
- 187