I try to find a polynomial for an arbitrary simple graph $G$ that tells whether the graph is connected or not. A graph is **st-connected** if you can find a path between a vertex $s$ and a vertex $t$ -- an example pair is sink and source.

A special case of this are vertex-induced subgraphs of $G$ and edge-induced subgraphs of $G$: suppose I know that $G$ is st-connected, is $G-v$ st-connected after a vertex deletion? Is $G\backslash e$ st-connected after an edge deletion?

*Random graph models*

Given a graph $G$, a

*vertex-induced random subgraph of $G$*is a new graph by vertex deletions and deletions of its incident edges with some probability $p$ on each vertex where vertices are independently deleted.*What is the connectivity polynomial in the vertex probability?*Given a graph $G$, a

*edge-induced random subgraph of $G$*is a new graph by edge deletions and deletions of isolated vertices with some probability $p$ on each edge where edges are independently deleted.*What is the connectivity polynomial in the edge probability?*

I am trying to understand the connectivity of the random graph models with Percolation theory here and here.

**Does there exist a polynomial for the connectivity of a simple graph?**

Given two vertices $s$ and $t$ and a graph $G$, which polynomial tells whether a path exist between $s$ and $t$ in $G$?

What is the connectivity polynomial for vertex-induced random subgraph?

What is the connectivity polynomial for the edge-induced random subgraphs?