**Motivating example.** Consider the graph $G=(V,E)$ with $V = \{0,1,2,3\}$ and $E = \big\{\{i,i+1\}: i\in \{0,1,2\}\big\}$. We have $\chi(G) = 2$, but if we collapse $0$ and $3$, we get the complete graph on $3$ points (having chromatic number $3$). Note that $0$ and $3$ have distance $3$.


**Problem statement.** If $G = (V,E)$ is a simple, undirected graph and $v\in V$, let $N(v) = \{w\in V: \{v,w\}\in E\}$. We say $x\neq y \in V$ have *distance 2* if $\{x,y\}\notin E$ but $N(x)\cap N(y) \neq \varnothing$. If $x\neq y \in V$ and $\{x,y\}\notin E$ we let define the graph $G/\{x,y\}$ by $V(G/\{x,y\}) = V \setminus \{x\}$ and $$E(G/\{x,y\}) = \{e \in E: y \notin e\}\cup\big\{\{x,z\}: z\in N(y)\big\}.$$


What is an example of a finite connected graph $G=(V,E)$ and $x\neq y\in V$ such that $x,y$ have distance 2 and $\chi(G) < \chi(G/\{x,y\})$?



Effect of collapsing two vertices of distance $2$
Add to your motivating example a fifth vertex called $4$ and make it adjacent to all of $0,1,2,3$. This graph is $3$-colorable (by the $2$-coloring of your example and a third color for vertex $4$) but if you collapse $0$ with $3$ you get the complete graph on $4$ vertices, which needs four colors. And the distance from $0$ to $3$ is $2$, via vertex $4$.


