Скажите ,а если Украины,что меняется?

То тогда от него возможно нужно разрешение на вывоз из Украины ребёнка

если отец гражданин Украины, то разрешение от него обязательно потребуется при выезде ребенка за пределы Украины. правило такое: Если ребенок, имеющий только украинское гражданство, выезжает за пределы Украины с одим из родителей, - требуется разрешение другого на выезд. Если ребенок выезжает один по детскому проездному или с бабушкой-дедушкой - требуется разрешение от обоих родителей. Если ребенок имеет немецкий киндеррайспасс, то есть является гражданином Германии, то никаких разрешений не нужно.
У меня старшая дочь летела первый раз одна в Германию ко мне, в детском проездном (украинском) - ауфэнтхальтэрлаубнис (вид на жительство), справка из ЗАГСа о том, что она - ребенок одинокой матери (это равнозначно разрешению отца), - не выпускали, так как не было моего нотариального разрешения на выезд с территории Украины.

во многом Вы правы.
Те, кого интересует "правило", могут ознакомиться с ним в разделах 2-1 и 2-2 вот этого документа:
http://zakon1.rada.gov.ua/cgi-bin/laws/main.cgi?nreg=57-95-%EF