In 1988 at a seminar in Oberwolfach (located in Germany and by many mathematicians considered as a sort of “mecca for mathematicians” [1]) the czech mathematician Jaroslav Nešetřil conjectured the following:

Nešetřil conjecture (informal). There exists only a finite number of finite minimal asymmetric graphs.

While significant progress towards the goal of proving the conjecture had been made, it still remained an open problem up until 2016 were the theorem was finally proven by the Schweitzer brothers [2]. To be precise, it was proven that:

Schweitzer theorem. There are exactly 18 finite minimal asymmetric undirected graphs up to isomorphism.

For a graph to be asymmetric, it should not offer any non-trivial automorphisms (with the trivial automorphism being the identity map). For recollection, an automorphism is loosely speaking the symmetry exposed by the graph, it is an isomorphism between two graphs $G,H$ (where isomorphism means we can map with $\phi$ between vertices of $G,H$ such that any $(a,b)\in E_G\iff (\phi(a),\phi(b))\in E_H$ where $E_X$ is the edge list of graph $X$) with the special case of $H:=G$ i.e., it remaps its own vertices and structure preserving all adjacencies and non-adjacencies. [3] provides a visual tutorial. Consider for instance the following example: $G=(\{ a,b,c,d\},\{a\leftrightarrow b\leftrightarrow c\leftrightarrow d\})$ so $G$ defines an undirected chain graph. The mapping $\phi = \{ a \mapsto d, b \mapsto b, c \mapsto c, d \mapsto a \}$ is not an automorphism, as can be easily seen since for instance since $(a,b)$ adjacent if and only if $(\phi(a), \phi(b))$ adjacent does not hold as $(d,b)$ are not adjacent. However, $\phi$ would be an isomorphism onto the graph $H=(\{a,b,c,d\},\{a\leftrightarrow c\leftrightarrow b\leftrightarrow d\})$ (note how $b$ and $c$ switched positions relative to $G$). Modifying $\phi$ slightly to account for the previous stage i.e., $\phi = \{ a \mapsto d, b \mapsto c, c \mapsto b, d \mapsto a \}$ would thus correct $\phi$ to be an automorphism on $G$ as it simply flips the graph left-right (mirrors using vertical axis). Finally, for a graph to be minimal asymmetric we say that it should not induce a proper subgraph that would again be asymmetric (i.e., the graphs identified by the theorem are in that sense elementary since none of them contains any of the other). To return to the Schweitzer theorem, consider Figure 1 which lists all of the 18 graphs:


Figure 1: All 18 finite minimal asymmetric graphs. For each graph the triple $(n, m, \hat{X})$, describes the number of vertices, edges and the name of the complement graph, respectively. The graphs are ordered first by number of vertices and second by number of edges.

For the actual proof and more details please consider the original work in [2]. This result arguably comes as a suprise, to further get an intuition in the scope of this short article, let’s consider the following example where we choose $G_1$ to be the smallest minimal asymmetric graph from Figure 1 ($G_1:=X_1$). No matter where we inject an additional edge into $G_1$, the resulting graph will not be minimally asymmetric anymore. Figure 2 visualizes two such interventions, which clearly reveal the new graph to contain non-trivial automorphisms i.e., symmetries.


Figure 2: Minimal Asymmetry. The two example modifications of $G_1$ have symmetry as their immediate consequence. The respective automorphisms: in Example 1, we can simply flip the resulting graph left-right while for Example 2 we can do it diagonally.

The theorem significanlty strengthens our understanding of graph auto-/isomorphism, extending a collection of knowledge (see e.g. [4]), however, future will tell how we might tackle the remaining open problems using the key insights from [2].

References

S. Buchholz, “Ein Mekka für Mathematiker – Oberwolfach”, Wave phenomena, 2016.
Pascal & Patrick Schweitzer, “Minimal Asymmetric Graphs”, Journal of Combinatorial Theory Vol. 127, 2017.
S. Herke, “Graph Theory FAQs: 02. Graph Automorphisms”, YouTube, 2015.
Wolfram Mathworld, “Graph Automorphism”, 2022.

Proving Nešetřil's Conjecture: Minimal Asymmetric Graphs