The Minimum Gap Graph Partitioning Problem consists in partitioning a vertex-weighted undirected graph into p connected subgraphs with minimum gap between the largest and the smallest vertex weight. In this work, we introduce the lexicographic version of the problem consisting in minimizing first the largest gap, then the sum of the gaps of all subgraphs. For this new variant we present a Ruin and Recreate solution approach, whose solution quality is assessed with the results provided by a mathematical programming formulation.