Lemma 1 The number of maximal cliques in (c-)max-tolerance graphs is O(n3).