The third-smallest asymmetric graph

The smallest asymmetric graph is the empty graph, and the second smallest is the one-vertex graph. What about the third-smallest?

Any two-vertex graph has a nontrivial automorphism (swapping the two vertices), so it can’t be a two-vertex graph.
Any vertex connected to all others or disconnected from all others could be removed without increasing the amount of automorphisms, so it can’t be any graph that has such a vertex. This means it can’t be any three-vertex graph.
Any disconnected graph would contain a smaller graph with at most as many automorphisms, so it can’t be a disconnected graph.
The complement of any graph has the same number of isomorphisms, so it can’t be the complmement of any already-excluded graph.
Any graph larger than 1 vertex that is isomorphic to its own complement has a non-trivial automorphism: applying said isomorphism twice. (Corollary: the third-smallest asymmetric graph is not unique)
The previous three sentences excluded the three remaining four-vertex graphs: complement of 4-cycle, 4-cycle, and path graph respectively.
Any remaining five-vertex graph with four edges must be a tree, and either include no vertices with degree larger than two (in which case it is the path graph, which has reversal as a non-trivial automorphism), or include one vertex with degree larger than two (in which case it can only include one such vertex and the distances from said vertex to the degree-one vertices cannot be all distinct, creating a non-trivial automorphism). This also excludes the five-vertex graphs with six edges (they are complements of five-vertex graphs with four edges).
The only remaining five-vertex graphs have five edges. Either they have five vertices of degree 2 (in which case it is the pentagon graph, which is isomorphic to its complement), three vertices of degree 2 and one vertex each of degree 1 and 3 (in which case it is a cycle graph with a stick attached, which has a non-trivial isomorphism of reversing the cycle), or one vertex of degree 2 and two vertices each of degree 1 and 3 (there is only one graph that has those degrees, so it’s isomorphic to its complement).

Therefore, the third-smallest asymmetric graph must have at least 6 vertices. There are asymmetric graphs with 6 vertices:

and their complements. I am uncertain of if those four are the only asymmetric graphs with 6 vertices.

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *