TAOCP 7.2.2.2 Exercise 317
Connection interrupted.
Section 7.2.2.2: Satisfiability
Exercise 317. ▶ [M26] Let $\alpha(G) = \Pr(\bar{A}_1 \cap \cdots \cap \bar{A}_m)$ under the assumptions of (133), when $p_i = p = (d-1)^{d-1}/d^d$ for $1 \le i \le m$ and every vertex of $G$ has degree at most $d > 1$. Prove, by induction on $m$, that $\alpha(G) > 0$ and that $\alpha(G) \ge \frac{d-1}{d} \alpha(G \setminus v)$ when $v$ has degree $< d$.
Verified: no
Solve time: 3m04s
Connection interrupted. Waiting for the complete answer