Editing Vertex-transitive graph (section)

{{Short description|Graph where all pairs of vertices are automorphic}}
{{Graph families defined by their automorphisms}}

In the [[mathematics|mathematical]] field of [[graph theory]], an [[Graph automorphism|automorphism]] is a permutation of the [[Vertex (graph theory)|vertices]] such that edges are mapped to edges and non-edges are mapped to non-edges.<ref name=Godsil01/>  A graph is a '''vertex-transitive graph''' if, given any two vertices {{math|''v''{{sub|1}}}} and {{math|''v''{{sub|2}}}} of {{mvar|G}}, there is an automorphism {{math|''f''}} such that
:<math>f(v_1) = v_2.\ </math>

In other words, a graph is vertex-transitive if its [[automorphism group]] [[Group action (mathematics)|acts]] [[Group_action#Remarkable properties of actions|transitively]] on its vertices.<ref name=Godsil01>{{citation|first1=Chris|last1=Godsil|authorlink1=Chris Godsil|first2=Gordon|last2=Royle|authorlink2=Gordon Royle|title=Algebraic Graph Theory|series=[[Graduate Texts in Mathematics]]|volume=207|publisher=Springer |orig-year=2001 |isbn=978-1-4613-0163-9 |year=2013|url=https://books.google.com/books?id=GeSPBAAAQBAJ }}.</ref> A graph is vertex-transitive [[if and only if]] its [[graph complement]] is, since the group actions are identical.

Every [[symmetric graph]] without [[isolated vertex|isolated vertices]] is vertex-transitive, and every vertex-transitive graph is [[Regular graph|regular]]. However, not all vertex-transitive graphs are symmetric (for example, the edges of the [[truncated tetrahedron]]), and not all regular graphs are vertex-transitive (for example, the [[Frucht graph]] and [[Tietze's graph]]).