The connected induced subgraph polynomial of a graph 
on 
vertices is the generating
function
 |
(1)
|
where 
is the number of connected
induced subgraphs of 
on 
vertices (Tittmann et al.
2011, Kroeker et al. 2018).
Suppose each vertex of 
is independently retained with probability 
and deleted with probability 
. Then
 |
(2)
|
is the probability that the retained vertices induce a connected induced subgraph, so
 |
(3)
|
For example, 
for a complete
graph, while 
for an empty graph
on 
vertices.
