You can boot a Linux installation on 4 megabytes of RAM, but GNOME takes another 50 or so, and for KDE you should have at least 128 MB.

(I won't argue with you when it comes to stuff like Fluxbox or E16, though. Or XFCE for that matter, but I hold the opinion that XFCE is ugly. :P )