If G is a subgraph of H then $p_c(G) \geq p_c(H)$

Question

I am trying to find a rigorous proof for If G is a subgraph of H then $p_c(G) \geq p_c(H)$

The statement is almost trivial but I cannot seem to prove it. Could anyone give some pointers for where to start?

Thanks :)

Answer 1

Ah, I see that you reformulated your previous question in a more general way. Because it might not be clear what $p_c$ means in a general graph setting, let me define it as $$p_c(G) = \inf \left\{p \colon \inf_{x,y\in G} \mathbb{P}[x\leftrightarrow y] >0 \right\}\,, $$ i.e. the lower bound on $p$ for which connectivity throughout the whole graph is present with positive probability. If $G$ is a 'subgraph' of $H$ (i.e. $G$ and $H$ have the same vertex set, while the edge set of $G$ is contained in the edge set of $H$), we can define a coupling between percolation on $G$ and percolation on $H$ in the following way: For an edge $e\in G$, let $e$ be open with probability $p$ and closed otherwise. If open, also declare $e\in H$ as open, otherwise closed. For edges $f\in H$ that are not in $G$, declare them open in $H$ probability $p$. This process generates configurations according to the $p$-percolation measure on $G$ and $H$, with the additional property that $$x\leftrightarrow y \text{ in } G \Rightarrow x\leftrightarrow y \text{ in } H $$ for all $x,y$. This implies $$ \mathbb{P}[x\leftrightarrow y \text{ in } G] \leq \mathbb{P}[x\leftrightarrow y \text{ in } H]$$ for all $x,y$, and therefore $p_c(G) \geq p_c(H)$. In words: The coupling shows that high connectivity in $G$ implies high connectivity in $H$.