Does an electrolytic capacitor have a minimum voltage?
For most practical purposes electrolytic capacitors can be considered to NOT have a minimum voltage rating.

The "problem" in your circuit that causes it to not work at less than 7V is that you are using a 12V relay as seen here. This is designed to operate to specification at 12V applied to coil but will pull in at somewhat less than 12V. How much less depends on various factors including the rate of rise of the applied voltage. Without knowing what is "out there" on your +12VDC supply it's not possible to give a full picture (and even then one would need to look at relay specs) but as you reduce Vin the capacitor charges in a "more leisurely" manner and at 7V the relay may still operate without the capacitor, even while being well below specified voltage, but with the capacitor the slow rise time defeats it.

It's possible that adding a large capacitor from relay center terminal to ground MAY allow lower voltage operation by making a larger source of surge current available. 



Here is the relay datasheet all the way from Ningbo (directly south of Shanghai across the very wide river delta). 

Guaranteed pull in voltage is >= 9.6V so 7V is "rather low".
Dropout MAY be as low as 0.6V!