Automorfizm grafu – wzajemnie jednoznaczne przekształcenie zbioru wierzchołków grafu w ten sam zbiór takie, że wierzchołki oraz są sąsiednie wtedy i tylko wtedy, gdy i są sąsiednie.
Definicja Formalnie automorfizmem grafu jest każdy izomorfizm z nim samym, a więc bijekcja
taka, że
gdzie oznacza zbiór wierzchołków , a zbiór jego krawędzi.
Szczególnym przypadkiem jest przekształcenie identycznościowe, które każdemu wierzchołkowi przypisuje jego samego. W kontekście automorfizmów przekształcenie to często nazywa się trywialnym automorfizmem i oznacza przez lub .
Grupa automorfizmów Zbiór automorfizmów dowolnego grafu wraz z dwuargumentową operacją ich składania tworzą jego grupę automorfizmów, zwykle oznaczaną przez . Aby przekonać się, że jest grupą, można zauważyć, że ma ona własności grupy: Wewnętrzność: dla dowolnych automorfizmów ze zbioru , złożenie również jest automorfizmem , Łączność: dla każdych należących do zachodzi , Element neutralny: przekształcenie identycznościowe na wierzchołkach należy do , Odwracalność: każdy automorfizm grafu z definicji jest odwracalny, a jego odwrotność również jest automorfizmem, więc dla każdego elementu w istnieje w , takie że .