Automorfizam grafa
Automorfizam grafa, svojstvo grafa u teoriji grafova. Predstavlja permutaciju skupa vrhova [math]\displaystyle{ V(G) }[/math] koja čuva susjednost. Grupa automorfizama [math]\displaystyle{ Aut(P) }[/math] Petersenova grafa je simetrična grupa [math]\displaystyle{ S_{5} }[/math] te je ukupan broj automorfizama jednak 120. Po Lovaszoj slutnji, graf [math]\displaystyle{ G }[/math] je tranzitivan po vrhovima ako za svaki par vrhova [math]\displaystyle{ u }[/math] i [math]\displaystyle{ v }[/math] iz [math]\displaystyle{ G }[/math] postoji automorfizam na [math]\displaystyle{ G }[/math] koji preslikava [math]\displaystyle{ u }[/math] u [math]\displaystyle{ v }[/math]. Još uvijek nije otkriven niti jedan graf koji je tranzitivan po vrhovima, a da nema Hamiltonov put. Slutnja se pokazala točnom za razne klase grafova, no još uvijek nije pronađen dokaz. [1]