In Book IX of the Elements, Euclid recorded a constructive proof that there are infinitely many prime numbers. It remains a model of elegant mathematical reasoning. However, some basic follow-up questions remain unanswered, such as: If we start from nothing and apply Euclid's construction in all possible ways, does every prime number eventually turn up? I will explain how the set of all possible instances of Euclid's construction has a natural directed graph structure, before saying some (interesting?) things about the graph.