The problem of the equipartitioning of a random graph of fixed finite valence is studied by comparison with a ferromagnetic Bethe lattice with random boundary conditions. The simplicity of recursion relations for effective fields due to descendents on Bethe lattices provides simple approximations for the optimal cost, in quite good agreement with simulations.