Core Gift Set + Adventurer's Vault (it's just two... err... items

).
The core rules are, even though the game is designed to be open for expansions, as complete as you would need them. I havn't really noticed any
lack in there, yet. They even have gnomes (in the MM)!
You can play Magic: the Gathering with nothing but the first set just fine as well (I'm sure if you couldn't it would hardly have the success it had, because it would have been a pretty pointless game to begin with back then

).
If you want some specific classes, you might be out of luck, but the core selection of eight classes is definitely enough to play the game.
Only the magic item section, while also ok, could need a bit more, hence the recommendation of Adventurer's Vault, which adds plenty enough to round up the selection. Of course, you could think those up yourself, as well.
I don't think you need more than those (even AV might not be necessary) to have fun with 4E.
Of course, you could also go with one of those one-book-games out there, which are very enjoyable as well, like Savage Worlds. If you prefer a condensed rules set.
Bye
Thanee