Abstract. We show, under a weak assumption on the term $p$, that a variety of general algebras satisfies the congruence identity $p(\alpha_1, \ldots, \alpha_n) \subseteq q(\alpha_1, \ldots, \alpha_n )$ if and only if it satisfies the tolerance identity $p(\Theta_1, \ldots, \Theta_n) \subseteq q(\Theta_1, \ldots, \Theta_n)$, provided we restrict ourselves to tolerances representable as $R \circ R^-$. Varieties in which every tolerance is representable include all congruence permutable varieties and all varieties of lattices. For arbitrary tolerances, the congruence identity $p(\alpha_1, \ldots, \alpha_n) \subseteq q(\alpha_1, \ldots, \alpha_n )$ is equivalent to the identity $p(\Theta_1 \circ\Theta _1, \ldots, \Theta_n \circ\Theta _n) \subseteq q(\Theta_1 \circ\Theta _1, \ldots, \Theta_n \circ\Theta _n)$. See Theorems 3, 4 and 5. Our arguments essentially deal with labeled graphs, rather than terms; we try to clarify the role of graphs in the study of Mal'cev conditions (see especially Proposition 21 and Theorem 22).

AMS Subject Classification (1991): 08A30, 08B05

Keyword(s): Congruence, tolerance identity, Mal'cev condition, labeled graph, regular term, representable tolerance

Received November 13, 2006, and in revised form February 17, 2007. (Registered under 5952/2009.)