# Question about uniquely colorable graphs

Let $$G$$ be a uniquely $$k$$-colorable graph (for a definition, see https://en.wikipedia.org/wiki/Uniquely_colorable_graph). Is it true that we can always find a vertex $$v$$ such that $$G-v$$ is again uniquely $$k$$-colorable? The answer is certainly 'yes' when $$k=2$$ and for the family of uniquely $$4$$-colorable Apollonian networks, but I have not yet been able to find a general proof, or a counter-example.

• A 1-vertex graph is still uniquely $k$-colorable for all $k$. The essence here is the partition in color classes. Dec 11, 2018 at 18:13
• $K_1$ is uniquely $2$-colorable: every $2$-coloring induces the same partition in color classes. Dec 11, 2018 at 18:15

There exist uniquely 3-colorable graphs without triangles. The one on Mathworld (http://mathworld.wolfram.com/Uniquelyk-ColorableGraph.html) is incorrect (it has two different colorings as you can easily see by evaluating its chromatic polynomial at $$k=3$$ and dividing by $$3!$$), but there are others.
If the answer would be "yes" you can keep removing single vertices until you have three vertices left. Since there still is no triangle, the result cannot be uniquely $$3$$-colorable.