Query regarding $k$-critical graphs I am studying coloring of graphs and having some basic doubts in the theorems regarding $k$-critical graph.
$\mathbf {Definition}$ - A graph $G$ is said to be $k$-critical if $ \chi (G) = k$ and $ \chi(H) < k$ for any proper subgraph $H$ of $G$.
Now all the theorems regarding $k$-critical graphs use the fact that – if $\chi(G) =k$ and $\chi(G \setminus v) <k$ for any vertex $v$ of $G$ , then $G$ is $k$-critical.
But I am not understanding how the above statement is equivalent to the definition. Because there may exist a proper subgraph $H$ of $G$ that has all the vertices of $G$. This may be very trivial but I am really struggling with this. Someone please help me to understand this.
Thank You.
 A: You are right and the people stating those theorems are (a little bit) wrong.
Unfortunately, many people talk about $k$-critical graphs when they really mean "$k$-vertex-critical". A $k$-vertex-critical graph is exactly one for which deleting any vertex reduces the chromatic number. Equivalently, any proper induced subgraph has a smaller chromatic number.
Just to make sure what you are saying is always clear, I would avoid using the term "$k$-critical graph" and only ever talk about "$k$-vertex-critical" and "$k$-edge-critical" graphs. Then it's clear that the second kind of graph really is sensitive to the removal of a single edge.
To reassure you that there really is a difference, consider the following graph, taken from the paper Efficient algorithms for finding critical subgraphs by Desrosiers, Galinier, and Hertz:

This graph has chromatic number $4$, and will continue to have chromatic number $4$ if the edge $v_1v_2$ is deleted, but if you delete any vertex, the result has chromatic number $3$.
