Sensitivity of Graph Properties
The survey that Suresh pointed to brings up a paper by Wegener [1] that partially confirms the conjecture. It holds for all monotone graph properties and the inequality is tight (consider the property "Has no isolated vertices"). Any more recent results would be appreciated as well.


Wegener, L. The critical complexity of all (monotone) Boolean functions and monotone graph properties. Information and Control, 67:212-222, 1985.