Minimum Weight Random Graphs with Edge Constraints

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.