Suppose we have $n$ horses. It suffices to show they are all the same color. We do so by induction on $n$.

If $n=0$ or $n=1$, then, certainly all $n$ horses are the same color, so the base case holds.

For the inductive hypothesis, assume we've shown that all the horses in any group of $n-1$ or fewer horses are the same color, and suppose we are faced with a group of $n$ horses. Choose some horse arbitrarily and remove it, leaving a group of $n-1$ horses for our consideration. By the induction hypothesis, these horses are all the same color. Replace the horse we removed and then remove a different horse from the group. Likewise, these horses are all the same color. This then implies that all $n$ horses are the same color. Since $n$ is arbitrary, this shows that all horses are the same color.