Frucht's theorem guarantees that every group arises as the automorphism group of some graph, but the classical proof relies on combinatorial constructions that implicitly invoke the axiom of choice in ways that become nontrivial when foundational assumptions are weakened. The question is whether, working purely in ZF without any choice principle, one can still realize every countably infinite group as the automorphism group of some graph, or whether there exist countably infinite groups in certain choiceless models of set theory for which no such graph exists. This is a precise and clean question sitting at the intersection of combinatorics and set-theoretic independence results.