Uma relação de equivalência sobre o conjunto de vértices de um grafo é um conjunto R de pares de vértices dotado das seguintes propriedades:

• reflexiva: para cada vértice x, o par (x,x) está em R;
• simétrica: se (x,y) está em R então (y,x) também está em R;
• transitiva: se (x,y) está em R e (y,z) está em R então (x,z) também está em R.

Toda relação de equivalência R impõe uma partição do conjunto de vértices: dois vértices x e y pertencem ao mesmo bloco da partição se e somente se (x,y) está em R.  Cada bloco da partição é conhecido como classe de equivalência.