In this paper we approximate the convex envelope of a boundary datum inside a bounded domain in the Euclidean space. We work with a random graph that is obtained as random points with uniform distribution that are connected by proximity ($x\sim y$ when $|x-y|<r$). On the graph we solve an equation (that approximate the first eigenvalue of the Hessian of a smooth function) with an exterior datum. Under appropriate assumptions on $r$ we show that the unique solution to the equation in the graph converges to the convex envelope of the boundary datum as the number of points goes to infinity.