# The effects of collapsing vs joining non-adjacent vertices on the chromatic number

For any set $$X$$, let $$[X]^2 = \big\{\{x,y\}: x\neq y \in X\big\}$$.

Is there a finite, simple, undirected, connected graph $$G=(V,E)$$ with the following properties?

1. There is $$\{v, w\}\in [V]^2\setminus E$$ such that collapsing $$v,w$$ increases the chromatic number, but
2. for all $$\{a, b\}\in [V]^2\setminus E$$ we have $$\chi((V,E)) = \chi((V, (E\cup\{a,b\})))$$, that is, adding an edge connecting $$a$$ and $$b$$ does not increase the chromatic number.

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.
• Here $50$ can be treated as a variable, whose smallest value seems to be $2$. Bigger values of $50$ have the advantage that you can add quite a few edges without increasing the chromatic number. – Andreas Blass May 19 at 16:25
• @AndreasBlass Indeed. We can even allow $N_G(v)$ and $N_G(w)$ to intersect if we like. Most values of $|N_G(v)|, |N_G(w)|$, and $|N_G(v) \cap N_G(w)|$ will give valid examples (this is basically a list colouring problem on $v$ and $w$). – Tony Huynh May 20 at 6:09