  We conduct a quantitative analysis on the number of random edges required to
be added to a base graph~$H$ to significantly increase natural minor-monotone
graph parameters in the resulting graph~$R$. Specifically, we show that if $R$
is obtained from a connected graph $H$ by adding only a few random edges, the
tree-width, genus, and Hadwiger number of $R$ become very large, irrespective
of the structure of~$H$.
