Let $G'$ be a graph obtained from $G$ after contracting each edge with probability $p$. Let $n = |V(G)|, e = |E(G)|$.


I would like to compute (or at least obtain a lower bound) for $E[|V(G')|]$ in terms of some known graph invariants (number of edges, degree sequence, connectivity,..)


I am sure I am not the first one that studied such a probabilistic space and since I couldn't find any estimates for $E[|V(G')|]$ in my textbook I am asking: is there any simple identity/estimate for $E[|V(G')|]$ ? Is there any reference to a paper studying this quantity?


**Edit**: I have removed the completely wrong attempt to estimate $E[|V(G')|]$.



Randomly contracting edges of a graph - expected number of vertices?
The expected number of vertices of $G'$ is given by a sum (over all sets of edges) that bears a certain resemblance to the Tutte polynomial $T(x,y)$ of (the graphical matroid associated to) $G$, as defined, for example, at <http://en.wikipedia.org/wiki/Matroid#Tutte_polynomial>. A quick calculation (maybe too quick --- I don't guarantee the following and I apologize for any errors here, but something like this should be true) indicates that, if we let $v,e,c$ be the number of vertices, edges, and components of $G$, then the expected number of vertices of $G'$ is 


$$c+p^{v-c}(1-p)^{e+c-v}\frac{\partial T(x,y)}{\partial x}\left(x=\frac1p,y=\frac1{1-p}\right).$$


EDIT:
In answer to the question about how I got this, and in the interest of correcting missing factors of $p$ and $1-p$ in the answer above, here are some details.


I'll use the notation $v,e,c$ as above. In addition, for any subset $S$ of the edges, I'll write $z(S)$ for the number of points after the edges in $S$ are contracted; it's also the number of connected components of the graph with the same vertices as $G$ but only the edges in $S$. Note that the rank of $S$ in the graphical matroid is $v-z(S)$. Obviously, $z(S)$ is always at least $c$; it turns out to be convenient to work with the difference, which I'll abbreviate $q(S)=z(S)-C$. Taking the definition of the Tutte polynomial $T(x,y)$ from the Wikipedia page linked above, and using the connection between ranks and $z$, we get
$$
T(x,y)=\sum\_{S\subseteq E}(x-1)^{z(S)-c}(y-1)^{|S|-v+z(S)}=
\sum\_{S\subseteq E}(x-1)^{q(S)}(y-1)^{|S|-v+c+q(S)}.
$$


Compare this with the expectation of $q$, namely
$$
\sum\_{S\subseteq E}q(S)p^{|S|}(1-p)^{|E|-|S|}=
(1-p)^{|E|}\sum\_{S\subseteq E}q(S)\left(\frac p{1-p}\right)^{|S|}.
$$


We can convert $T(x,y)$ into this expectation in a few steps, as follows. First, if we differentiate $T(x,y)$ with respect to $x$ and multiply the result by $x-1$, the effect is to bring down a factor $q(S)$ from the exponent without changing anything else. That factor $q(S)$ matches part of what we want in the expectation of $q$. Next, we can make the $x-1$ and $y-1$ stuff in $T$ match the $p$ and $1-p$ stuff that we want. First set $y-1=p/(1-p)$; equivalently, $y=1/(1-p)$. Then the terms in $T$ will have the factor $(p/(1-p))^{|S|}$ that we want. They also have other factors that we don't want, namely $(x-1)^{q(S)}$ and $(p/(1-p))^{-v+c+q(S)}$. We can get rid of the $q(S)$ powers here by setting $x-1=(1-p)/p$; equivalently $x=1/p$. What remains is an unwanted factor $(p/(1-p))^{-v+c}$ that doesn't involve $S$ and can therefore be pulled out of the sum. Collecting all this stuff (and hoping that I'm copying everything correctly --- copying is sometimes the hardest part of mathematics), I get that the expectation of $q$ is 
$$
(1-p)^e\cdot \left[\left((x-1)\frac{\partial T(x,y)}{\partial x}\right)
(\frac1p,\frac1{1-p})\right]\cdot\left(\frac p{1-p}\right)^{v-c},
$$
which simplifies to 
$$
p^{v-c-1}(1-p)^{e+c-v+1}\frac{\partial T}{\partial x}\left(\frac1p,\frac1{1-p}\right).
$$
Finally, add $c$ to get the expectation of $z$.


