I'm trying to solve two problems about graph automorphisms.
- I want to construct a bipartite graph without a nontrivial automorphism.
- 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?
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.
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.