A classic problem arising in classication consists in summarizing a collection C, called a profile, of p equivalence relations defined on a finite set X by an equivalence relation E* at minimum remoteness from C. The remoteness is based on the symmetric dierence distance and measures the total number of disagreements between E* and C, and then E* is called a median equivalence relation of C. It is usual to summarize C by its majority graph. We study the converse issue. We give a sufficient condition for a graph to be the majority graph of a profile of equivalence relations. We then deduce from this that the computation of E* is NP-hard when p is large enough.