# Graphs without nontrivial automorphism

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?

 Does this one have a nontrivial automorphism?

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:

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.

• 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. Jun 19, 2014 at 23:25
• Okay, thanks, that confirms what I have so far. But how can I prove that no such graph with $5$ nodes exists? Jun 19, 2014 at 23:27
• 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. Jun 19, 2014 at 23:32
• 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? Jun 19, 2014 at 23:44
• 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. Jun 19, 2014 at 23:54

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.