What are the critical files a theme MUST have to be a WordPress theme and validate properly?
The bare minimum required is your index.php file and style.CSS file. Those two files alone are technically enough to run your entire theme. It's highly unlikely that you'll rely on those two alone.
The above link gives you an in-depth look at both the minimum and recommended requirements.
For example I run one theme with an index.php, functions.php, style.css and a loop.php and templates.php file. It's a complete custom job that relies on the heavy use of filters to create a modular way of delivering content with a minimal setup. You won't encounter themes like this very often, but it does illustrate the possibilities and power of Wordpress theming which don't always have to follow the norm.
Themes intended for release at the wordpress.org public theme repository however, follow a stricter set of guidelines, regardless of the above. This is more so to ensure consistency and interoperability when changing from theme to theme as people who use free themes often do