# Decreasing the chromatic number by $2$ by removing $2$ well-chosen vertices

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?

1. For every $$v\in V$$ there is $$w\in V\setminus \{v\}$$ such that $$\{v,w\}\notin E$$, and
2. there are $$v\neq w\in V$$ such that $$\chi(G\setminus\{v,w\}) = \chi(G)-2$$.
• Take any bipartite graph that has a 4-cycle. Add the two diagonals to make a 4-clique. Then the chromatic number is 4 but you can bring it down to 2 by removing two vertices. Commented Feb 2, 2021 at 10:28
• OK cool - you want to post it as an answer? Otherwise I'll remove my question Commented Feb 2, 2021 at 10:32
• Maybe you can think of a deeper version? Commented Feb 2, 2021 at 10:36
• Yes, maybe. Meanwhile, I'll remove the question. - Thanks again for your example! Commented Feb 2, 2021 at 11:33
• @bof Yes, I only claimed to answer it for $n=4$. Commented Feb 3, 2021 at 6:25

Let $$G_0=(V_0,E_0)$$ be a complete graph of order $$n\ge4$$. Choose two distinct points $$a,b\in V_0$$ and two distinct points $$x,y\notin V_0$$. The graph $$G=(V,E)$$ with vertex set $$V=V_0\cup\{x,y\}$$ and edge set $$E=E_0\cup\{\{a,x\},\{b,y\}\}$$ satisfies your requirements with $$\chi(G)=n$$.