For a phylogeny reconstruction problem, 
Desper and Gascuel proposed Greedy Minimum Evolution algorithm (in short, GME) and 
Balanced Minimum Evolution algorithm (in short, BME).
Both of them are faster than the current major algorithm, 
Neighbor Joining (in short, NJ);
however, less accurate when an input distance matrix has errors.
In this paper, we prove that BME has the same optimal robustness
to such errors as NJ but GME does not.
Precisely, we prove that if the maximum distance error is less than 
a half of the minimum edge length of the target tree, 
then BME reconstruct it correctly.
On the other hand, there is some distance matrix such that 
maximum distance error is less than $\frac{2}{\sqrt{n}}$ 
of the minimum edge length of the target tree,
for which GME fails to reconstruct the target tree.