Number of automorphisms in a graph

Question

I have searched all over YouTube and Google about finding the number of all possible automorphisms in a graph, but couldn't find anything except some trivial examples. I would like to know how you would approach this type of problem, also would appreciate useful links/documents.

Our lecturer told us to fix points one by one in a process, but his explanation was simply horrible. I have tried solving multiple problems, but 90% of times I get the wrong answer, thanks in advance.

For example how would you count the number of automorphisms for octahedron graph:

Answer 1

For a general graph this is a hard problem and no polynomial-time algorithm is known. It is of equivalent complexity to the graph isomorphism problem. This is known to be solvable in quasipolynomial time (a recent, and very famous, result of Babai) and probably most experts expect it to be NP-intermediate.

So there is no hope of an effective general method to do this. For a particular small graph there may well be a simple ad-hoc method to count the automorphisms, though.

[edit] You now ask about the octahedron. We can label the vertices $u,v,w, u',v',w'$, where $u$ is adjacent to all vertices except $u'$, etc. Now $u$ can map to any of the $6$ vertices, and $u'$ must map to the opposite vertex. $v$ can now map to any of the remaining $4$ vertices, and $v'$ must go to the opposite vertex. Finally $w$ can map to either of the other $2$ vertices. This gives $6\times 4\times 2=48$ automorphisms.

Answer 2

An automorphism of a graph is a bijection of the vertices that also preserves the edges. A graph with $n$ vertices has exactly $n!$ different bijections of the vertices and this list gives you all possible candidates for automorphisms. So if you want to find all automorphisms of a particular (small) graph you can look at the edge bijections and then exclude all those that can't be an automorphism. The solution for the octahedron graph that Especially Lime describes does essentially that. Due to the high symmetry and looking at the vertices in a clever order, only very cases need to be actually checked.