Number of vertices in $k$-critical graphs

Question

Let $G=(V,E)$ be a simple, undirected graph. We call it $k$-critical if $\chi(G)=k$ and removing any vertex decreases the chromatic number.

The odd circles $C_{2n+1}$ are all 3-critical. By taking any odd circle and adding a point $\infty$, connecting it to all points in the circle, we get a $4$-critical graph. Similar constructions give rise to the following observation:

If $n \geq k \geq 3$ are positive integers and the difference $n-k$ is even, then there is a an edge set $E$ on $\{1,\ldots, n\}$ such that $(\{1,\ldots,n\},E)$ is a $k$-critical graph.

Does the converse hold, that is: if $(\{1,\ldots,n\},E)$ is a $k$-critical graph, is the difference $n-k$ even?

Answer 1

(I extend my previous comment to this answer.)

I have found (by computer) several examples for that the converse does not hold. The smallest ones are 4-critical graphs on seven vertices. There are (up to isomorphism) exactly seven 4-critical graphs on 7 vertices. One example is the graph $G = (V,E)$ where $V = \{1,2,\dots,7\}$ and $E = \{(1, 3), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 6), (3, 7), (4, 6), (4, 7), (5, 7)\}$, also illustrated in the following figure:

I have also found exactly seven 5-critical graphs on 8 vertices, seven 6-critical graphs (and also a lot of 4-critical graphs) on 9 vertices and seven 7-critical graphs on 10 vertices.