For a given subcritical discrete Schr\"odinger operator $H$ on a weighted infinite graph $X$, we construct a Hardy-weight $w$ which is {\em 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.
