Let $G = (V, E)$ be non oriented graph.
A vertex $v$ is called critical if $\chi (G-v) <\chi (G)$.
An edge $e$ is called critical if $\chi (G-e) < \chi (G)$.
Finally $G$ is vertex critical if every vertex is critical. I have seen a result which give an example (http://www.sciencedirect.com/science/article/pii/0012365X9290354I little complicated) of vertex critical graph without critical edge. My question is there a simple example of vertex critical graph with at least one non critical edge ?
An example is the graph $C_7^2$ pictured below.
This graph has chromatic number 4. To prove this, try going around the outside cycle coloring the vertices in order. Any three adjacent vertices must have different colors. So if we only had three colors, then our coloring would be fixed: it would have to go "red, blue, green, red, blue, green, ...". When we get to the last vertex, it's supposed to be colored red, but it's already adjacent to a red vertex: the first vertex. So 3 colors is not enough, but 4 is: just color the last vertex yellow.
From this proof, we can see that the graph is vertex-critical: we finished coloring the entire graph, except for the last vertex, with three colors (you should check that there's no conflict between the first vertex and the next-to-last vertex along the cycle). So if we deleted the last vertex, the chromatic number would go down to 3. By symmetry, this is true for any vertex.
However, we can also see from this proof that the graph has non-critical edges. In our argument for why three colors don't work, we never even used the edge between the last vertex and the second vertex. So if we delete that edge (or any one of the other "diagonal" edges) then the chromatic number remains at 4.