Probably by removing MySQL rpms (preferably using yum or other package manager) and then installing the MySQL 4 rpms. I don't think MySQL will be a problem; if I remember correctly, it doesn't have too many dependencies, so actually you'll only have to remove one or two (or so) MySQL packages, and probably (depending on how you implement MySQL database) some other packages, like php-mysql for example.
You should be able to just try
and get an error with some dependencies that'd break. Then you know which packages need MySQL. Then go googling and check out if you need to downgrade them too, or do they work with MySQL 4; if they do work, then just force-remove MySQL 5 and install MySQL 4. If they need downgrading, you simply need to obtain the correct (older) versions of them and do the downgrade job, and possibly get an error of some dependencies and solve them out too.
But as I said, I don't think it's too great a job for MySQL; I'd guess it's a small number of packets you need to get, downgrade and reinstall.
For example (these packages are imaginary) if you tried removing mysql and it told you that php-mysql and xxx-mysql packages need it, you would first find out what versions of mysql work with those. You'd then learn that (for example) php-mysql works with mysql5 only, but xxx-mysql would work with version 4 too; then you'd force-remove MySQL5, downgrade php-mysql, install MySQL4, perhaps reinstall xxx-mysql to be sure and try.
The big problem may occur if a package X needs the version 5 of MySQL, and downgrading that you'd get to know that package Y needs the specific version of package X and so on. It's a dependency hell of one kind, but as I said, I don't think MySQL leads to such a thing. At least it was so simple to install last time I tried that I don't think downgrading it is a headache.
