I'm trying to solve two problems about graph automorphisms.

  1. I want to construct a bipartite graph without a nontrivial automorphism.
  2. I want to find the smallest possible number of nodes for a graph without a nontrivial automorphism.

For 1, I basically tried a brute-force approach: I started with two disjoint sets of nodes of unequal size and drew edges where nodes were easily exchangable. However, it didn't really work. At least for $(2,3)$-graphs I wasn't able to come up with the desired property and I have no idea how many nodes I should use. (More than the answer to problem 2 of course...) What would be a clever approach, other than try and error?

[edit] Does this one have a nontrivial automorphism?

enter image description here

For 2, I wasn't more creative than that. I tried a lot of examples to develop some intuition. I'm pretty confident that a graph without nontrivial automorphisms has to have at least $5$ nodes and I think I've found a counter-example for $6$ nodes:

enter image description here

This one has no nontrivial automorphism, right? However, I'm unsure whether there is also a counter-example for $5$ nodes and if not, how could I prove that there is none? Sadly, it's also not a bipartite graph.

  • 1
    $\begingroup$ The smallest graph, bipartite or not, with a trivial automorphism group has $6$ nodes. I don't have a more clever way of proving that than by exhaustion, but that would work. $\endgroup$
    – Alexander Gruber
    Jun 19, 2014 at 23:25
  • $\begingroup$ Okay, thanks, that confirms what I have so far. But how can I prove that no such graph with $5$ nodes exists? $\endgroup$
    – Amarus
    Jun 19, 2014 at 23:27
  • $\begingroup$ You're only worried about bipartite graphs, right? There are only $5$ (connected) bipartite graphs on $5$ nodes. So, you could just find those and check their automorphism groups. $\endgroup$
    – Alexander Gruber
    Jun 19, 2014 at 23:32
  • $\begingroup$ Actually, problem 2 is not only about bipartite, but general graphs. I also edited the starting post with a possible bipartite example without nontrivial automorphism that I'm not one hundred percent sure about, but I think it has none, does it? $\endgroup$
    – Amarus
    Jun 19, 2014 at 23:44
  • $\begingroup$ Easy way of proving that your six-node graph has no non-trivial automorphism: the degrees of the nodes are 4, 3, 3, 2, 1, 1 so you only have to worry about distinguishing the degree-3 nodes and the degree-1 nodes. But one of your degree-3 nodes is connected to a degree-1 node and the other one isn't; and one of your degree-1 nodes is connected to a degree-4 node while the other is connected to a degree-3 node. $\endgroup$ Jun 19, 2014 at 23:54

1 Answer 1


An exhaustive search (using a software package such as SAGE) would show that the smallest asymmetric graph has 6 vertices, and in fact that there is a unique asymmetric graph on 6 vertices of smallest size (the size of a graph is the number of edges). This graph is obtained by just taking a path graph on 5 vertices, and then joining the 3rd and 4th vertex of this path to a common neighbor (vertex 6). So it's a path graph with a triangle on one side of the path, making the graph asymmetric.

Simulations confirm there are a total of 8 graphs on six vertices that are asymmetric. Except for the graph mentioned in the previous paragraph, the remaining 7 graphs each have at least 7 edges.

A simple way to construct an asymmetric bipartite graph on $n$ vertices (for any $n \ge 7$) is to construct a tree, with a designated vertex as root, and with three paths of different lengths emanating from this root vertex. For example, to construct an asymmetric tree on 7 vertices, take three paths of lengths 1, 2 and 3, respectively, emanting from a vertex. Since the root is the unique vertex of degree 3 in such a graph, the root must be fixed by any automorphism. Since the paths have different lengths, the tree has no nontrivial automorphisms.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .