How new?
Any Air that came with Lion or Mountain Lion would have a recovery partition. Press command-r to open it and reformat the drive and reinstall the OS.
If it's a Air that came with Snow Leopard, a little USB flash drive came with them to reinstall the OS.
As far as I recall, no Air ever had DVDs shipped with them.