# Criticalness and Hamiltonicity

Let $n\geq 2$ be an integer and suppose that the finite, simple, undirected graph $G=(V,E)$ is $n$-critical (that is, $\chi(G) = n$, and removing any vertex decreases the chromatic number).

This implies that $G$ is connected, but does $G$ necessarily have a path visiting every vertex exactly once?

Could this be a counterexample for $n=4$? I need to double check it.

• Yes, this is a counterexample. – Gordon Royle Feb 18 '17 at 2:35

This is some Sage code to check the counterexample posted by user1272680. I can't put this in a comment, so I am putting it as an answer, but the credit should go to user1272680.

g=Graph(21)
print g.chromatic_number()
for e in g.edges():
h = g.copy()
h.delete_edge(e)
print h.chromatic_number()
gd = g.to_directed()
[p for p in gd.all_simple_paths() if len(p) == gd.num_verts()]


First it constructs the graph, checks that it is 4-chromatic, runs through each edge and checks that the edge-deleted graph is 3-chromatic.

Finally it confirms that there are no hamilton paths - Sage apparently only has an "all paths" command for directed graphs, so I just turn the graph into a digraph where each edge becomes two opposite-directed arcs.