Yikes!!!
The problode is due to switching large currents through the relay coil,which will generate a large voltage across the coil when the magnetic field collapses.
The solution is to put a diode across the coil with the cathode connected to VCC which then gives a path for the high voltage spikes that are generated.
The voltage generated is given by
-ldi/dt
where l is the inductance of the coil