En grafautomorfi er en kortlægning af et sæt af hjørner på sig selv, der bevarer tilstødende. [1] Sættet af sådanne automorfier danner en topgruppe af en graf eller blot en grafgruppe . Permutationsgruppen på sættet af kanter kaldes grafens kantgruppe , som er tæt beslægtet med toppunktsgruppen:
En grafs kant- og toppunktsgrupper er isomorfe, hvis og kun hvis der højst er et isoleret toppunkt , og der ikke er nogen forbundne komponenter bestående af en enkelt kant. [2]
En graf, hvor den eneste mulige automorfi er identitetskortet, kaldes asymmetrisk. Det mindste asymmetriske træ har syv hjørner, og den mindste asymmetriske graf har seks hjørner og det samme antal kanter.
For enhver endelig gruppe er der en endelig urettet graf, således at dens automorfigruppe er isomorf med den givne. [3] Resultatet blev opnået af R. Frucht, beviset er baseret på transformationen af gruppens farvede graf , en generalisering af Cayley-grafen . [4] [5]