In the recent past, there has been considerable interest in the use of several Proximity Graphs for pattern recognition purposes. In particular, the Gabriel Graph and the Relative Neighbourhood Graph have successfully been applied to Prototype Selection (that is, editing and condensing) for the Nearest Neighbour classification rule. Nevertheless, after editing the initial training set, it is necessary to recompute the whole graph once again in order to apply condensing. From a practical point of view, this constitutes an important drawback due to the large computational cost required to construct these geometric structures. In this paper, a simple and fast algorithm to partially recompute a Proximity Graph is introduced. Experiments on synthetic and real databases are carried out to investigate the benefits of the algorithm in terms of running time.