The version I know goes on at greater length.
LEMMA: All horses are the same colour.
PROOF: By induction. Suppose that we have proved that any set of N
horses has the same colour. (The case N=1 is trivial.) Now consider a
set of N+1 horses. Remove one of them. The remainder have the same
colour, by the inductive argument. Now put that one back, and remove a
different one. Again, the remaining N horses have the same colour.
Therefore, this set of N+1 horses has the same colour.
THEOREM: All horses have an infinite number of legs.
PROOF 1: As outlined above by Richard.
PROOF 2: In case you find Proof 1 unconvincing, here is another approach
to the same result.
Suppose that somewhere there is a poor crippled horse with only a finite
number of legs. That would be a horse of a different colour, and that's
impossible by the Lemma.