It is proved that classical BRS-invariance of the Lagrangian implies perturbative gauge invariance for tree diagrams to all orders. The proof applies in particular to the Einstein Hilbert Largrangian of gravity.