Un automorfism de grafic este o mapare a unui set de vârfuri pe sine care păstrează adiacența. [1] Mulțimea unor astfel de automorfisme formează un grup de vârfuri al unui graf, sau pur și simplu un grup de graf . Grupul de permutare pe setul de muchii se numește grupul de muchii al graficului , care este strâns legat de grupul de vârfuri:
Grupurile de muchii și vârfuri ale unui grafic sunt izomorfe dacă și numai dacă există cel mult un vârf izolat și nu există componente conexe constând dintr-o singură muchie. [2]
Un grafic pentru care singurul automorfism posibil este harta identității se numește asimetric. Cel mai mic arbore asimetric are șapte vârfuri, iar cel mai mic grafic asimetric are șase vârfuri și același număr de muchii.
Pentru orice grup finit, există un graf finit nedirecționat astfel încât grupul său de automorfism este izomorf cu cel dat. [3] Rezultatul a fost obținut de R. Frucht, demonstrația se bazează pe transformarea grafului colorat al grupului , o generalizare a grafului Cayley . [4] [5]