Can contracting an edge increase the chromatic number by more than one? When you take an even cycle, $C_{2n}$, contracting an edge increases the chromatic number by $1$.
Can contracting an edge increase the chromatic number by more than one?
 A: Suppose edge $v_1v_2$ is contracted to $v_3$ and $v_1$ originally connected to set of vertices $S_1$, $v_2$ originally connected to $S_2$. 
When $v_1v_2$ is contracted $v_3$ is connected to $S_1 \cup S_2$ and nothing other than $\{v_3\}\cup S_1 \cup S_2$ has changed connectivity. So if we give $v_3$ a new color that was not originally in the graph, it will do us the trick and hence it is not possible we need two new colors.
A: I would say no. I have to go give a class now but I think the proof would be something like this:
Take a valid coloring of the initial graph, contract an edge between vertices $v_0$ and $v_1$ and give the vertex which results from merging $v_0$ and $v_1$ the color $v_0$ had in the initial coloring. If this coloring is not valid, then there has to be a neighbor of $v_1$ which had the same color as $v_0$. By coloring every such vertex (i.e. every neighbor of $v_1$ which has the same color as $v_0$) with a new color, we get a valid coloring of the contracted graph.
Since this is a method how we can create a valid coloring from each valid coloring of the initial graph by adding only one color, the chromatic number of the contracted graph is at most the chromatic number of the initial graph plus $1$.
A: Let $G$ be a graph with chromatic number $k$ then $k = \min \{n\in \mathbb{N}\mid P(G,n) \neq 0\}$ where $P(G,n)$ is the chromatic polynomial.
If when we contract the edge $uv$ the chromatic polynomial increases by more than one, then $P(G/uv,k+1) = 0$. From $P(G-uv,k+1) = P(G/uv,k+1) + P(G,k+1)$ it follows that $P(G-uv,k+1) = P(G,k+1)$, in other words, the edge $uv$ does not create any restriction on the coloring of the polynomial with $k+1$ colours.
That means that the graph is such that for any $k+1$-coloring of the graph $G-uv$, the vertex $u$ and the vertex $v$ are assigned different colours.
But we can create a $k+1$-coloring of the graph $G-uv$ such that $u$ and $v$ share a color as follows:
Take the $k$-coloring of the graph $G$ and apply it to $G-uv$. Color any vertex connected to $u$ that shares color with $v$ with the new color. Now color $u$ with the same color as $v$.
Therefore such graph does not exist.
