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).
If every vertex of 
operates independently with probability 
,
then
 |
(2)
|
is the probability that the operating vertices induce a connected induced subgraph, so
 |
(3)
|
For example, 
for a complete
graph, while 
for an empty graph
on 
vertices.
