-
A graph is asymmetric if its automorphism group is the identity group.
-
(Godsil 2.3.3) Almost all graphs are asymmetric.
-
Proof: Let the proportion of asymmetric isomorphism classes on
be . Note that the proportion of asymmetric graphs will be larger than so gives a lower bound. Each isomorphic class of a graph that is not asymmetric contains at most
graphs. On the other hand, by (Godsil 2.3.2), the average size of an isomorphism class is at most
And
Observe that
.
-