It is entirely possible to use the same power supply for both the Arduino and the relay, provided you are careful with the wiring layout. The bigger problem is to prevent the transients caused when the relay switches the load on or off from interfering with the Arduino.