  A random 2-cell embedding of a given graph $G$ is obtained by choosing a
random local rotation around every vertex. We analyze the expected number of
faces of such an embedding, which is equivalent to studying its average genus.
In 1991, Stahl proved that the expected number of faces in a random embedding
of an arbitrary graph of order $n$ is at most $n\log(n)$. While there are many
families of graphs whose expected number of faces is $\Theta(n)$, none are
known where the expected number would be super-linear. This lead to the
conjecture that there is a linear upper bound. In this note we confirm the
conjecture by proving that for any $n$-vertex multigraph, the expected number
of faces in a random 2-cell embedding is at most $n(1+H_m)$, where $m$ is the
maximum edge-multiplicity and $H_m$ denotes the $m$th harmonic number. This
bound is best possible up to a constant factor.

Combinatorics