  We show that the only random orderings of finite graphs that are invariant
under isomorphism and induced subgraph are the uniform random orderings. We
show how this implies the unique ergodicity of the automorphism group of the
random graph. We give similar theorems for other structures, including, for
example, metric spaces. These give the first examples of uniquely ergodic
groups, other than compact groups and extremely amenable groups, after Glasner
and Weiss's example of the group of all permutations of the integers. We also
contrast these results to those for certain special classes of graphs and
metric spaces in which such random orderings can be found that are not uniform.
