  A graph $G$ is a prime distance graph (respectively, a 2-odd graph) if its
vertices can be labeled with distinct integers such that for any two adjacent
vertices, the difference of their labels is prime (either 2 or odd). We prove
that trees, cycles, and bipartite graphs are prime distance graphs, and that
Dutch windmill graphs and paper mill graphs are prime distance graphs if and
only if the Twin Prime Conjecture and dePolignac's Conjecture are true,
respectively. We give a characterization of 2-odd graphs in terms of edge
colorings, and we use this characterization to determine which circulant graphs
of the form $Circ(n, \{1,k\})$ are 2-odd and to prove results on circulant
prime distance graphs.
