at least half the valency.

Published in: J. Comb. Theory, Ser. A (2012)