**Question:** In graph theory, contracting an edge or deleting an edge are *basic* operations in many topics such as [graph minors](http://en.wikipedia.org/wiki/Graph_minor) or [Wagner's theorem](http://en.wikipedia.org/wiki/Wagner's_theorem) on planar graphs. And I'm interested in how these operations affect [chromatic number](http://mathworld.wolfram.com/ChromaticNumber.html), which is the smallest number of colors needed to color the vertices of a graph so that adjacent vertices have different colors.


**Maybe... :** My guess is that these operation *never* increases the chromatic number of any graph because, roughly speaking, contraction-deletion makes a graph 'less complicated'. (Excuse my sloppy expression.) For example, a planar graph is 4-colorable even after deletion-contraction operations because they preserve planairty. 


**Maybe not... :** But pondering about [Braess's paradox](http://en.wikipedia.org/wiki/Braess's_paradox), which states that adding a route can cause overall traffic delays to worsen, I'm guessing this question may not be trivial at all and my intuition about deletion-contraction may be wrong.




---


* Is my question about chromatic number under deletion-contraction trivially true?
* If not, is there any paper about this topic?
* Is my *conjecture* true in a restricted setting, such as "A deletion-contraction operation in a planar graph never increases the chromatic number"?



How does deletion-contraction affect chromatic number? Can it increase chromatic number?
Your question is trivially false. Contracting an edge in an even cycle increases the chromatic number. Deleting edges never increase the chromatic number however, a coloring stays a coloring after deleting an edge.


