  We present the notion of \emph{reasonable utility} for binary mechanisms,
which applies to all utility functions in the literature. This notion induces a
partial ordering on the performance of all binary differentially private (DP)
mechanisms. DP mechanisms that are maximal elements of this ordering are
optimal DP mechanisms for every reasonable utility. By looking at differential
privacy as a randomized graph coloring, we characterize these optimal DP in
terms of their behavior on a certain subset of the boundary datasets we call a
boundary hitting set. In the process of establishing our results, we also
introduce a useful notion that generalizes DP conditions for binary-valued
queries, which we coin as suitable pairs. Suitable pairs abstract away the
algebraic roles of $\varepsilon,\delta$ in the DP framework, making the
derivations and understanding of our proofs simpler. Additionally, the notion
of a suitable pair can potentially capture privacy conditions in frameworks
other than DP and may be of independent interest.
