Gaussian graphical models are nowadays commonly applied to the comparison of groups sharing the same variables, by jointly learning their independence structures. We deal with a family of coloured Gaussian graphical models suited for paired data problems. The implementation of greedy search procedures for these models requires the exploration of the search space, that is challenging due to the dimensionality of the model space and the complexity of identifying neighbouring models. We consider the Edwards-Havránek coherent model selection procedure and show how to obtain some relevant quantities required for its implementation.