First, all the different EDITIONS of DnD are completely different games, and they are not compatible with each other.
On the other hand, the regular and deluxe 4th edition books are the same. The deluxe books have the errata corrections in the text, and are of slightly higher (but not necessary) production values. You can use either book interchangeably.
The BARE minimum needed to play is the Players Hand Book (PHB). Ideally everyone in your group should have their own copy, but you can get away with one with a little work.
Also at least one person per gaming group will need the Dungeon Master Guide (DMG) and the Monster Manuel (MM).
You should also have a full set of dice, lots of paper, and some pencils. I would recommend going online and printing your own copies of the character sheets.
The newer versions of the core books: Players Handbook 2, Dungeon Master Guide 2, and Monster Manuel 2 just expand on what is in the original books. They are not required to play, and in fact are not stand alone books, you must still have the PHB to have the core rules to play with.
So to summarize, you at least need the Player's Handbook to play, along with a set of dice. Beyond that, additional books give you more options, but are not required.