Graafinen automorfismi on pistejoukon kartoitus itseensä, joka säilyttää vierekkäisyyden. [1] Tällaisten automorfismien joukko muodostaa graafin kärkiryhmän tai yksinkertaisesti graafiryhmän . Reunajoukon permutaatioryhmää kutsutaan graafin reunaryhmäksi , joka liittyy läheisesti kärkiryhmään:
Graafin reuna- ja kärkiryhmät ovat isomorfisia silloin ja vain, jos on korkeintaan yksi eristetty kärki , eikä yhdestä reunasta koostuvia toisiinsa liittyviä komponentteja ole. [2]
Graafia, jonka ainoa mahdollinen automorfismi on identiteettikartta, kutsutaan epäsymmetriseksi. Pienimmässä epäsymmetrisessä puussa on seitsemän kärkeä ja pienimmässä epäsymmetrisessä graafissa kuusi kärkeä ja sama määrä reunoja.
Mille tahansa äärelliselle ryhmälle on olemassa äärellinen suuntaamaton graafi siten, että sen automorfismiryhmä on isomorfinen annetun kanssa. [3] Tuloksen sai R. Frucht, todistus perustuu ryhmän värillisen graafin muuntamiseen, Cayley-graafin yleistykseen . [4] [5]