Return to Revisions

Yes, such a graph does exist. Let $G$ be obtained from the complete graph $K_{100}$ by adding two non-adjacent vertices $v$ and $w$ such that $|N_G(v)|=|N_G(w)|=50$ and $N_G(v) \cup N_G(w)=V(K_{100})$. Here, $N_G(v)$ denotes the set of vertices of $G$ which are adjacent to $v$. Then collapsing $v$ and $w$ in $G$ yields $K_{101}$, which increases the chromatic number. On the other hand, it is easy to see that adding any edge to $G$ does not increase the chromatic number.