We identify the locally finite graphs that are quantifier-eliminable and their first order theories in the signature of distance predicates. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim.

We characterize Borel line graphs in terms of 10 forbidden induced subgraphs, namely the nine finite graphs from the classical result of Beineke together with a 10th infinite graph associated with the equivalence relation $\mathbb {E}_0$ on the Cantor space. As a corollary, we prove a partial converse to the Feldman–Moore theorem, which allows us to characterize all locally countable Borel line graphs in terms of their Borel chromatic numbers.