  For a given subcritical discrete Schr\"odinger operator $H$ on a weighted
infinite graph $X$, we construct a Hardy-weight $w$ which is optimal in the
following sense. The operator $H - \lambda w$ is subcritical in $X$ for all
$\lambda < 1$, null-critical in $X$ for $\lambda = 1$, and supercritical near
any neighborhood of infinity in $X$ for any $\lambda > 1$. Our results rely on
a criticality theory for Schr\"odinger operators on general weighted graphs.
