  Let $G$ be a permutation group on a set $\Omega$. A subset of $\Omega$ is a
base for $G$ if its pointwise stabiliser in $G$ is trivial. In this paper we
introduce and study an associated graph $\Sigma(G)$, which we call the Saxl
graph of $G$. The vertices of $\Sigma(G)$ are the points of $\Omega$, and two
vertices are adjacent if they form a base for $G$. This graph encodes some
interesting properties of the permutation group. We investigate the
connectivity of $\Sigma(G)$ for a finite transitive group $G$, as well as its
diameter, Hamiltonicity, clique and independence numbers, and we present
several open problems. For instance, we conjecture that if $G$ is a primitive
group with a base of size $2$, then the diameter of $\Sigma(G)$ is at most $2$.
Using a probabilistic approach, we establish the conjecture for some families
of almost simple groups. For example, the conjecture holds when $G=S_n$ or
$A_n$ (with $n>12$) and the point stabiliser of $G$ is a primitive subgroup. In
contrast, we can construct imprimitive groups whose Saxl graph is disconnected
with arbitrarily many connected components, or connected with arbitrarily large
diameter.
