Existence of a Connectivity Polynomial for a simple graph? 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?

 A: An answer which seems snide (but isn't!) is
$$P(G)=x^k$$ where $k$ is the number of connected components. Another which is possible but maybe not as reasonable is the constant polynomial $Q(G)=k.$
Recall that a proper coloring has vertices connected by an edge required to have unequal colors. Define $\chi (G,c)$ to be the number of proper colorings of $G$ with $c$ colors. It turns out this is a polynomial in $c$ which can (perhaps with some effort) be calculated recursively by the relations


*

*$\chi(s)=x$ for a graph $s$ consisting of a single point

*$\chi(G)=\chi(H)\chi(H')$ if $G$ is the union of disjoint graphs $H,H'$

*$\chi(G)=\chi(G-e)-\chi(G_e)$  Where $G-e$ is $G$ with the edge $e$ removed (but endpoints retained) and $G_e$ is $G$ with the endpoints of $e$ identified (and resulting multiple edges replaced with a single edge.)
Define a highly improper coloring to be one where vertices connected by an edge are required to have the same color and let $P(G,c)$ be the number of highly improper colorings with $c$ colors. This turns out to be a polynomial, in fact the one given above. It is no effort to compute but there are relations which are almost the same:


*

*$P(s)=x$ for a graph $s$ consisting of a single point

*$P(G)=P(H)P(H')$ if $G$ is the union of disjoint graphs $H,H'$

*$P(G)=P(G_e).$ 
Of course it is also easy to get $Q(G)=k$ with 


*

*$Q(s)=1$ for a graph $s$ consisting of a single point

*$Q(G)=Q(H)+Q(H')$ if $G$ is the union of disjoint graphs $H,H'$

*$P(G)=P(G_e).$ 
