If you remove any $2$ vertices from a complete graph, the chromatic number gets decreased by two. (The famous double-critical graph conjecture is about the existence of a non-complete graph such that any $2$ connected vertices can be removed such that the chromatic number of the graph decreases by $2$.)
Now there is a kind of graph where you can pick some $2$ points and get the chromatic number decreased. Let $C_{2n+1}$ for $n>2$ be the "circle" graph on $2n+1$ points, and add a "top" point $t$ to it, and connect $t$ to every other point. The chromatic number of that graph is $4$. If you remove $t$ and some other point, then the chromatic number of the resulting graph is $2$. The question is if you can construct a similar example without having to resort to a "top node" $t$ as above, which is connected to everything else. More formally:
Question. Given a positive integer $n\in\mathbb{N}$, is there a connected graph $G = (V,E)$ with $\chi(G) \geq n$, having the following properties?
- For every $v\in V$ there is $w\in V\setminus \{v\}$ such that $\{v,w\}\notin E$, and
- there are $v\neq w\in V$ such that $\chi(G\setminus\{v,w\}) = \chi(G)-2$.