First of all, I apologise if my question is not very specific. I am not really looking for a concrete answer but rather some hints and pointers what could be used/applied in this situation. A concrete example of how this is handled in practice would be nice too!
I read the very interesting article Terence Tao wrote about the crossing number inequality: http://terrytao.wordpress.com/2007/09/18/the-crossing-number-inequality/
I was wondering, how could one apply the same trick to other graph invariants where the amplified inequality only applies to connected graphs. More formally:
Let $i:G \mapsto \mathbb{R}$ be some graph invariant $f,g$ functions such that the inequality:
$i(G) \geq f(|V(G)|) + g(|E(G)|)) \;\;\;\;(1) $
holds for all connected graphs $G$.
Let $G'$ be the graph obtained from $G$ after we remove some of the vertices (or edges) with probability $p\in [0,1]$.
In the same manner as with the crossing number inequality, one would like to apply the inequality to $G'$ and examine the expected value of the obtained quantities. That is:
$E(i(G')) \geq E(f(|V(G')|)) + E(g(|E(G')|)) \;\;\;\;(2)$.
The problem with the last inequality is that it only holds when $G'$ is connected,which needs not to be. The obvious way to fix the problem is to modify $(1)$ so that it holds even when $G$ is not connected. In practice it can be hard to modify $(1)$ and still obtain a bound that will give a good inequality when estimating $(2)$.
So my question is: is there any known trick to force $G'$ to remain connected or somehow "handle" the disconnectedness case?
