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.

1 Answer 1


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.

  • 1
    $\begingroup$ 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. $\endgroup$ Commented May 19, 2020 at 16:25
  • $\begingroup$ @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$). $\endgroup$
    – Tony Huynh
    Commented May 20, 2020 at 6:09
  • $\begingroup$ Beautiful example, thanks @TonyHuynh! $\endgroup$ Commented May 20, 2020 at 7:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.