Prove that all graphs $G=(V,E)$ with $|V|=4$ have non-trivial automorphism group

Question

My understanding of this so far is that for $G$ to have a non-trivial automorphism group, ${\rm Aut}(G)$ must be greater than $1$ and therefore there exists a non-trivial symmetry of the vertices of $G$, i.e. not the identity. Hence, $G$ is symmetric (not asymmetric). So to prove all graphs on $4$ vertices have non-trivial automorphism group I can prove that there are no asymmetric graphs on $4$ vertices.

I believe my reasoning is correct but I don't know how to proceed from here. If anyone could help I would really appreciate it.

Answer 1

This is,of course, a matter of a finite check that you can leave to a computer. However, for a "manual" proof, we need a way to classify the (numerous) cases.

First notice that a graph with $4$ nodes cannot have all the degrees of those nodes different. Namely, there is no graph with precisely the degrees $0,1,2,3$, because the node with degree $0$ is not linked to any nodes, while the node with degree $3$ is linked to all nodes, including the former - a contradiction.

Thus, we can distinguish the cases based on the degree of two nodes with the same degree:

• If there are two nodes of degree $0$, a non-trivial automorphism will just swap those two nodes.
• If there are two nodes (say $A$ and $B$) of degree $1$, then: either they are linked to the same node (say $C$) and a non-trivial automorphism just swaps $A$ with $B$, or they are linked to different nodes (say $C$ and $D$, respectively), and a non-trivial automorphism maps $A\mapsto B, B\mapsto A, C\mapsto D, D\mapsto C$.
• If two nodes (say $A$ and $B$) are of degree $2$ or $3$, then consider the complement graph of the original graph. In the complement graph, $A$ and $B$ are of degree $1$ or $0$, respectively. Thus (as per the previous two points), there is a nontrivial automorphism of the complement graph. The same map is then a nontrivial automorphism of the original graph.