  A pair of orthonormal bases is called mutually unbiased if all mutual
overlaps between any element of one basis with an arbitrary element of the
other basis coincide. In case the dimension, $d$, of the considered Hilbert
space is a power of a prime number, complete sets of $d+1$ mutually unbiased
bases (MUBs) exist. Here, we present a novel method based on the graph-state
formalism to construct such sets of MUBs. We show that for $n$ $p$-level
systems, with $p$ being prime, one particular graph suffices to easily
construct a set of $p^n+1$ MUBs. In fact, we show that a single $n$-dimensional
vector, which is associated with this graph, can be used to generate a complete
set of MUBs and demonstrate that this vector can be easily determined. Finally,
we discuss some advantages of our formalism regarding the analysis of
entanglement structures in MUBs, as well as experimental realizations.
