  In a recent Letter we have shown that in shift-symmetric Horndeski theory the
scalar field is forced to obtain a nontrivial configuration in black hole
spacetimes, unless a linear coupling with the Gauss-Bonnet invariant is tuned
away. As a result, black holes generically have hair in this theory. In this
companion paper, we first review our argument and discuss it in more detail. We
then present actual black hole solutions in the simplest case of a theory with
the linear scalar-Gauss-Bonnet coupling. We generate exact solutions
numerically for a wide range of values of the coupling and also construct
analytic solutions perturbatively in the small coupling limit. Comparison of
the two types of solutions indicates that non-linear effects that are not
captured by the perturbative solution lead to a finite area, as opposed to a
central, singularity. Remarkably, black holes have a minimum size, controlled
by the length scale associated with the scalar-Gauss-Bonnet coupling. We also
compute some phenomenological observables for the numerical solution for a wide
range of values of the scalar-Gauss-Bonnet coupling. Deviations from the
Schwarzschild geometry are generically very small.
