Let G be a k-critical graph, where $k≥3$. Show that $G$ has at least $k+2$ vertices?

Question

Let $G$ be a $k$-critical graph, where $k≥3$, and let u and v be two distinct vertices of $G$. Show that $u$ has a neighbor which is not a neighbor of $v$. Hence show that G has at least $k+2$ vertices.

This is a problem in my graph theory textbook, A First Look At Graph Theory by Derek Holton and John Clark. Its definition of a $k$-critical graph is

A graph $G$ is called $k$-critical if $\chi(G) = k$ and $\chi(G-v) < k$ for each vertex $v$ of $G$.

I am confused on this problem because I believe I have found a contradiction to this statement.

Here is my thought process so far. I started looking at graphs that are at least 3-critical.

These graphs are 3-critical and satisfy the statement having "at least" $k+2$ vertices.

Then I looked at the complete graph $k3$. . This graph is 3-critical but contradicts the statement if $G$ is $k$-critical and $k≥3$ then show $G$ has "at least" $k+2$ vertices.

I am confused if I am reading this problem wrong or my book has a typo.

I want to complete this problem. I am hoping the book has a typo. I am also hoping there is something that I am missing here.

Thank you, please help, and have fun!

Answer 1

You are correct that $K_3$ is a counterexample: its chromatic number is $3$, and if you delete any vertex, then the chromatic number will go down by $1$. In fact, $K_k$ is also a $k$-critical graph: its chromatic number is $k$, and if you delete any vertex, then the chromatic number will go down by $1$. That is also a counterexample to this statement.

I have no clue if I'm fixing a typo or making up a new exercise here, but the problem could have said:

Let $G$ be a $k$-critical graph, where $k\ge3$, other than the complete graph $K_k$, and let $u$ and $v$ be two distinct vertices of $G$ with no edge between them. Show that $u$ has a neighbor which is not a neighbor of $v$. Hence show that $G$ has at least $k+2$ vertices.

Of course, in any graph that is not a complete graph, there exist two distinct vertices with no edge between them. So this shows that there is no $k$-critical graph with $k+1$ vertices: you have $K_k$, with $k$ vertices, and all other $k$-critical graphs have at least $k+2$.

---

Also, this does not really affect the problem, but this book is committing a grave error by using the terms "chromatic number" and "chromatic index" interchangeably. Virtually all graph theorists use "chromatic number", denoted $\chi(G)$, to refer to the minimum number of colors in a proper vertex coloring, and "chromatic index", denoted $\chi'(G)$, to refer to the minimum number of colors in a proper edge coloring.

I am not too fond of this terminology; I think "edge chromatic number" would be better than "chromatic index". Regardless, the fact remains that if you use "chromatic index" to refer to $\chi(G)$, you will confuse anyone that did not learn graph theory from the same source.