A gráf automorfizmus csúcsok halmazának önmagára való leképezése, amely megőrzi a szomszédosságot. [1] Az ilyen automorfizmusok halmaza egy gráf csúcscsoportját, vagy egyszerűen egy gráfcsoportot alkot . Az élhalmaz permutációs csoportját a gráf élcsoportjának nevezzük , amely szorosan kapcsolódik a csúcscsoporthoz:
A gráf él- és csúcscsoportjai akkor és csak akkor izomorfak, ha legfeljebb egy elszigetelt csúcs van, és nincsenek egyetlen élből álló összefüggő komponensek . [2]
Aszimmetrikusnak nevezzük azt a gráfot, amelynek egyetlen lehetséges automorfizmusa az identitástérkép. A legkisebb aszimmetrikus fának hét csúcsa van, a legkisebb aszimmetrikus gráfnak pedig hat csúcsa és ugyanannyi éle van.
Bármely véges csoporthoz létezik olyan véges irányítatlan gráf, amelynek automorfizmuscsoportja izomorf az adott csoporthoz. [3] Az eredményt R. Frucht kapta, a bizonyítás a csoport színes gráfjának transzformációján, a Cayley-gráf általánosításán alapul . [4] [5]