  In structural pattern recognition, given a set of graphs, the computation of
a Generalized Median Graph is a well known problem. Some methods approach the
problem by assuming a relation between the Generalized Median Graph and the
Common Labelling problem. However, this relation has still not been formally
proved. In this paper, we analyse such relation between both problems. The main
result proves that the cost of the common labelling upper-bounds the cost of
the median with respect to the given set. In addition, we show that the two
problems are equivalent in some cases.
