  In this paper we introduce the concept of clique disjoint edge sets in
graphs. Then, for a graph $G$, we define the invariant $\eta(G)$ as the maximum
size of a clique disjoint edge set in $G$. We show that the regularity of the
binomial edge ideal of $G$ is bounded above by $\eta(G)$. This, in particular,
settles a conjecture on the regularity of binomial edge ideals in full
generality.
