Frucht's theorem is a result from graph theory stating that every abstract group can be realized as the symmetry group of some graph. This turns out to be a surprisingly delicate statement from the perspective of the foundations of mathematics. The paper investigates exactly how much set-theoretic machinery is needed to prove it, focusing on two standard axioms: the axiom of choice, which says you can always make selections from collections of sets, and the axiom of foundation, which rules out circular or infinitely descending set membership. The surprising finding is that Frucht's theorem requires both axioms in some form, meaning it fails in set-theoretic universes where either one is absent.
To explore this, the authors construct a kind of map showing how Frucht's theorem and related variants relate to these axioms. They use two main tools. The first is the construction of specific infinite graphs with carefully controlled symmetry properties. The second is the technique of permutation models, which are deliberately weakened mathematical universes where certain axioms fail, allowing the authors to demonstrate that particular theorems genuinely cannot be proved without those axioms. By combining provability results with these unprovability constructions, they can precisely locate each principle in the logical landscape.
The broader significance is that this opens a new direction in set theory. Researchers have long studied which mathematical statements follow from or are independent of the axiom of choice, and separately have studied the role of the axiom of foundation. This paper begins charting the much less explored territory where both axioms are absent simultaneously, using a concrete and familiar mathematical theorem as the entry point. The result is a preliminary map of an area that had not previously been systematically investigated.