We apply the objective method of Aldous to the problem of finding the minimum cost edge-cover of the complete graph with random independent and identically distributed edge-costs. The limit, as the number of vertices goes to infinity, of the expected minimum cost for this problem is known via a combinatorial approach of Hessler and Wastlund. We provide a proof of this result using the machinery of the objective method and local weak convergence, which was used to prove the zeta(2) limit of the random assignment problem. A proof via the objective method is useful because it provides us more information on the nature of the edges incident on a typical root in the minimum cost edge-cover. We further show that a belief propagation algorithm converges asymptotically to the optimal solution. The belief propagation algorithm yields a near optimal solution with lesser complexity than the known best algorithms designed for optimality in worst- case settings.