Abstract Algebra: Theory and Applications · Problem 14.9.3
The Sylow Theorems — Thomas Judson
Mathematics — Abstract Algebra · trivial-automorphism-group-graph
Problem
Construct a simple graph (no loops or multiple edges), with at least two vertices and at least one edge, whose automorphism group is trivial. You might start experimenting by drawing pictures on paper before constructing the graph. A command like the following will let you construct a graph from edges. The graph below looks like a triangle or 3-cycle. \begin{verbatim} G = Graph([(1,2), (2,3), (3,1)]) G.plot() \end{verbatim}Intuitive explanation
A graph's automorphism group captures all the symmetries—the ways you can relabel vertices while preserving edges. To get a trivial automorphism group, you need a graph with no symmetry at all: no two vertices can "look the same" in terms of their connections. The key insight is that if every vertex has a different degree (number of neighbors), or if the neighborhood structure is sufficiently asymmetric, then the only automorphism is the identity. Try building a small path or tree where vertices have distinct degrees, then verify no non-trivial relabeling preserves the edge structure.
Intuitive explanation
A graph's automorphism group captures all the symmetries—the ways you can relabel vertices while preserving edges. To get a trivial automorphism group, you need a graph with no symmetry at all: no two vertices can "look the same" in terms of their connections. The key insight is that if every vertex has a different degree (number of neighbors), or if the neighborhood structure is sufficiently asymmetric, then the only automorphism is the identity. Try building a small path or tree where vertices have distinct degrees, then verify no non-trivial relabeling preserves the edge structure.