  In this paper we extend our techniques, developed in a previous paper (Du,
etc, JHEP 05(2016)086) for direct evaluation of arbitrary $n$-point tree-level
MHV amplitudes in 4d Yang-Mills and gravity theory using the Cachazo-He-Yuan
(CHY) formalism, to the 4d Einstein-Yang-Mills (EYM) theory. Any single-trace
color-ordered $n$-point tree-level MHV amplitude in EYM theory, obtained by a
direct evaluation of the CHY formula, is of an elegant factorized form of a
Parke-Taylor factor and a Hodges determinant, much simpler and more compact
than the existing formulas in the literature. We prove that our new expression
is equivalent to the conjectured Selivanov-Bern-De Freitas-Wong (SBDW) formula,
with the help of a new theorem showing that the SBDW generating function has a
graph theory interpretation. Together with Ref. (Du, etc, JHEP 05(2016)086), we
provide strong analytic evidence for hidden simplicity in quantum field theory.
