  In this paper, we study two examples of minimum weight random graphs with
edge constraints. First we consider the complete graph on ${n}$ vertices
equipped with uniformly heavy edge weights and use iteration methods to obtain
deviation estimates for the minimum weight of subtrees with a given number of
edges. Next we analyze edge constrained minimum weight paths in the integer
lattice ${\mathbb{Z}^d}$ and employ martingale difference techniques to
describe the behaviour of the scaled minimum weight in terms of the edge
constraint.
