A classical theorem of Frucht states that any finite group appears as the automorphism group of a finite graph. In the quantum setting the problem is to understand the structure of the compact quantum groups which can appear as quantum automorphism groups of finite graphs. We discuss here this question, notably with a number of negative results.