Technically, a Voltage regulator is an OP AMP with a voltage reference. Look at the design of a legacy LM723.http://www.national.com/ds/LM/LM723.pdf
I think you are thinking about this too hard. You are describing regulator "drop out", which a regulator like a LM7805 will want to do somewhere between 6 and 7 volts.
Now, if you wanted to do this with a little bit more control... start looking at circuits based on the LM431. IN the design ideas section of the data sheet, there is "Over Voltage/Under Voltage
Protection Circuit" or a "Voltage Monitor" as good ideas to think about. http://www.national.com/ds/LM/LM431.pdf
...and "no" using a relay is not a good idea. It makes the solution too complicated. Simply pinching off a PASS TRANSISTOR is probably the best solution.