Breaking graph symmetries by edge colourings

Abstract

The distinguishing index $D^{\prime }(G)$ of a graph $G$ is the least number of colours needed in an edge colouring which is not preserved by any non-trivial automorphism. Broere and Pilśniak conjectured that if every non-trivial automorphism of a countable graph $G$ moves infinitely many edges, then $D^{\prime }(G)\le 2$. We prove this conjecture.