Regular graph with no non-trivial automorphim

Question

I am looking for a regular graph example which has no automorphism other than identity (trivial).

I tried for complete graphs, cycle, and some more regular graphs, but they are not the valid examples. I am looking for an easy example.

Answer 1

One construction for cubic graphs is to draw a tree with all vertices of valency one or three in the plane, then draw a cycle through the vertices of degree one. This gives you a planar cubic graph and, provided your initial tree is large enough, it is not hard to produce graphs witn no non-identity automorphisms. And the point is that you can verify by hand that your graph is asymmetric. (These graphs are sometimes referred to as Halin graphs.)

You can also use Latin square graphs, but now you need a computer to determine the automorphism group. Here the vertices are the $n^2$ position in an $n\times n$ Latin square, and two positions are adjacent if they are in the same row, the same column, or if they have the same entry. You'll need $n\ge 5$ to have a chance of an asymmetric graph, but for large $n$ most choices work. (Don't choose the multiplication table of a group!)

Answer 2

The Frucht graph on 12 vertices is 3-regular and is asymmetric.

See the Wikipedia articles on "Frucht graph" and "asymmetric graph". The smallest asymmetric regular graphs have 10 vertices.