Graphs without nontrivial automorphism 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.
 A: 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.
