Trees are almost prime

Let SnSn denote the graph on {1,…,n}{1,…,n} in which two numbers are adjacent if and only if they are coprime. Around 1980 Entringer conjectured that SnSn contains every tree of order n as a subgraph.Here we show that this conjecture is true for all n⩽50n⩽50. Further positive evidence is provided by our main result that SnSn contains every tree of order (1-o(1))n(1-o(1))n.