Grafo de Frucht
No campo da matemática da teoria dos grafos, o Grafo de Frucht é um grafo 3-regular com 12 vértices e 18 arestas e nenhuma simetria não-trivial. Foi descrito pela primeira vez por Robert Frucht em 1939.
O grafo de Frucht é o menor grafo cúbico possuindo somente um único automorfismo de grafos, a identidade(ou seja, cada vértice pode ser distinguido topologicamente de todos os outros vértices). Tais grafos são chamados assimétricos (ou identidade). O teorema de Frucht diz que qualquer grupo pode ser compreendido como o grupo de simetrias de um grafo, e um reforço deste teorema também devido à Frucht afirma que qualquer grupo pode ser percebido como as simetrias de um grafo 3-regular; o grafo de Frucht fornece um exemplo desta realização para o grupo trivial. O polinômio característico do grafo de Frucht é igual a ( x − 3 ) ( x − 2 ) x ( x + 1 ) ( x + 2 ) ( x 3 + x 2 − 2 x − 1 ) ( x 4 + x 3 − 6 x 2 − 5 x + 4 ) {\displaystyle (x-3)(x-2)x(x+1)(x+2)(x^{3}+x^{2}-2x-1)(x^{4}+x^{3}-6x^{2}-5x+4)} .
