# Number of vertices in $k$-critical graphs

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?

• My computer claims that there are (seven) 4-critical graphs on 7 vertices. For example the graph G=(V,E) where V = {1,2,...,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)}. (There are also seven 5-critical graphs on 8 vertices, and seven 6-critical graphs on 9 vertices - but also a lot of 4-critical graphs on 9 vertices). – Oliver Krüger Mar 6 '17 at 15:16
• Oh -- that's nice, can you put this as an answer? – Dominic van der Zypen Mar 7 '17 at 12:27
• Ok. It has been done. – Oliver Krüger Mar 7 '17 at 12:49

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: