What is a disequality path in the context of equality graphs?
Suppose we have a bunch of variables $v_i$ and a bunch of equations $v_i = v_j$ and disequalities $v_i \neq v_j$. We can describe out knowledge as a graph whose vertices are the variables and whose edges are the equations (equality edges) and disequalities (disequality edges).
An equality path is a proof that $v_i = v_j$. Such a proof consists of a path from $v_i$ to $v_j$ using only equality edges. A disequality path is a proof that $v_i \neq v_j$. Such a proof consists of a path from $v_i$ to $v_j$ in which exactly one edge is a disequality edge.
When the domain of the variables is larger than 2, then equality paths are the only way to deduce equality from the givens, and disequality paths are the only way to deduce disequality from the givens. This is a nice exercise. In the binary case, however, a path with an even number of disequality edges is a proof of equality, and a path with an odd number of disequality edges is a proof of disequality.