A finite, simple, undirected graph $G=(V,E)$ is said to be *(vertex)-critical* if removing any vertex decreases its [chromatic number](https://en.wikipedia.org/wiki/Graph_coloring). By $\delta(G)$ we denote the *minimum degree* of $G$. The *degeneracy* of $G$ is defined by $$\text{degen}(G) = \max\{\delta(H): H \text{ is an induced subgraph of }G\}.$$
Obviously, for any graph $G$ we have $\delta(G) \leq \text{degen}(G)$.


**Question.** Is there a vertex-critical graph $G$ such that $\delta(G) < \text{degen}(G)$?



Degeneracy vs minimal degree in critical graphs
There is such a graph, provided by the graph6 string



```
U???????wE?kAgWoAdGpQQ`GdA^?ldgsRW[C~w??

```

and is [uploaded to the House of Graphs](https://hog.grinvin.org/ViewGraphInfo.action?id=48171).


The graph is critical, as verified by the SageMath code:



```
a=Graph('U???????wE?kAgWoAdGpQQ`GdA^?ldgsRW[C~w??');
a.chromatic_number() #returns 5
for p in a.vertices():
    b=a.copy()
    b.delete_vertex(p)
    if b.chromatic_number()==5:
        print('The graph is not critical');
        break

```

(You should not see the message "The graph is not critical".)


The graph has minimum degree $4$ and degeneracy at least $5$:



```
a.degree(0) #returns 4
a.delete_vertex(0);min(a.degree()) #returns 5

```

