What is the minimum required set of parts for Mindstorms?
I would get the NXT brick itself, at least one but preferably two motors, and the touch sensor.

Obviously, you need a brain brick, but you also need a way for it to do something, thus the motors. And if you want to do anything particularly interesting, that doesn't need to be automatic functions only, you'll need a sensor to start different functions at the proper times and in the proper conditions.

You could expand a little by adding the motion detector, but mostly you just need an input, output, and brain.