Prime sum graphs and the induced trees they contain

In this paper we show that prime sum graphs on $n$ vertices – which are graphs on vertex set $\{1,2,\mathrm{.}\mathrm{.}\mathrm{.},n\}$ where $ij$ is an edge when $i+j$ is prime – contain all trees with at most $\exp (c\log n\mathrm{/}\log \log n)$ vertices as induced subgraphs. We also prove some results for related graphs, and end with some unsolved problems.