I am doing this post in parts. For those wanting more while they wait I direct you to 319906.

Let's start with the multigraph (two vertices having multiple edges) case, and worry about the big cliques in this multigraph first. If $n$ is a multiple of 2, we have $n/2$ even numbers and $n/2$ choose 2 edges between them. If $n$ is not a multiple of 2, replace $n/2$ by floor or ceiling of $n/2$, which ever applies.

We can make a similar statement for larger primes $p \lt n$, but I will write 3 for $p$: the interval has $k$ multiples of $3$ and the graph thus has $k$ choose 2 edges between these multiples, where $k$ is floor or ceiling of $n/3$. Even if we don't know $n$, we know there will be something near $n^2/18$ number of edges, and I could write a more exact expression that is within $ 1 + n/3$ of the correct number of edges.

The point is that there is a $C$ so that for $n$ not too small the multigraph will always have close to $Cn^2$ edges with an uncertainty generously bounded by $n(1+ \log\log n)$. This $C$ actually varies slightly with $n$ but for many practical purposes is well approximated by (1/2) (1/4 + 1/9 + 1/25), so I will write 1/4 for $C$ and talk about its exact value later.

Now the problem above deals with a graph, not a multigraph, and the rough estimate above counts graph edges more than once. In the interval, every set of multiples of an odd prime $p$ has half or almost half of those multiples which are even, and so about a quarter of the edges of that clique of multiples belong to the clique of even numbers already. So the number of multigraph edges overshoots the number of graph edges by a factor of close to (1/4)(1/9 + 1/25 + ...). The point here is that an upper bound for the number of graph edges is given by an estimate of multigraph edges, while a lower bound can be gotten by looking at the edges between multiples of the two or the three smallest primes in the interval, and the two numbers will not be very far apart.

Coming next: Some extreme examples.

**Edit 2019.02.27:**

Seva has in the meantime provided a post containing figures for a related quantity. While I suspect there are some corrections still to be made in that post, I think the order of growth is correct. I will now talk about the graphs for small $n \gt 1$.

It should be noted that an edge occurs only when two numbers share at least one prime factor less than $n$, and therefore the graph for an interval is identical (up to labelling) to one for the interval shifted by a multiple of the appropriate primorial. (We can use symmetry about 0 to consider only about half of the intervals less than the primorial.) So for small $n$ we can quickly check our work.

We ignore n=1 and note n=2 is the two-point empty graph. For n=3 we may also have a path of length one if the interval has two even numbers otherwise it is the empty graph again. For n=4, we have at least one edge for even numbers, and sometimes may have one additional edge attached to this edge for multiples of 3.

Now we observe some general properties. There may be a dense collection of coprimes (numbers not having prime factors less than n) in this interval. So the graph may have infinite diameter. However, among all vertices with positive degree, they will be an even number or adjacent to an even number, so the largest connected component has diameter at most 3, and all other connected components have diameter 0. It is clear that for each n one can find a graph of diameter 3 (include appropriately placed multiples of primes p and q where both are less than n and larger than n/2), and I suspect for n sufficiently large one can always find such a graph with diameter 2 (or even connected component with diameter 2), but this suspicion smells of Goldbach and de Polignac, so I stay uncommitted on the diameter two issue. (Actually, let the interval have a multiple of the primorial, then the connected component has diameter two.)

We have each graph has a clique of about n/2 vertices, one of about n/3 vertices with about half of those vertices shared by the large clique, and one can extend this to cliques of about n/p vertices for primes larger than p. Here is a nice observation: the multiples of p in an interval form an arithmetic progression where, if one looks at gcd between these members divided by p, one gets a smaller graph that looks like one of the graphs on n/p vertices. Thus one can use smaller bounds to predict how much a p-clique shares with cliques induced by smaller primes.

Turning to n=5, we have one graph which has only one edge, one with two edges (and therefore a path), and graphs which have a triangle and possibly one more edge, giving a range of 1 to four edges in the connected component, and always at least one isolated vertex.

For n=6 we always have a component that contains a triangle plus an edge, and sometimes there is one more edge. This gives three possibilities up to isomorphism, with 4 or 5 edges and Max vertex degree is 3 or 4.

Indeed, when n is a primorial (product of primes up to k), every interval has its graph sharing a common subgraph which are the edges induced by multiples of primes up to k. If n is larger than this primorial, there is still the subgraph on the vertex subset representing (say) the left half of the interval, so many of the edges can be quickly determined.

For n=7 we may have any combination of 3 or 4 even numbers in the interval, 2 or 3 multiples of three, and one or two multiples of five, ranging from a low of 4 edges to a high of 9 edges. If there are 9 edges, the connected component has a diameter of two and one isolated vertex, and the 4 edge and 6 edge examples are also unique.

For n=8 we have a clique with six edges, and in addition to the possibilities for three and for five we have the option of an additional edge for multiples of seven. This gives graphs ranging from 7 edges up to 11 edges.

Up next: better numerics.

**End Edit 2019.02.27.**

Gerhard "Holds The Post Serialization Rights" Paseman, 2019.02.26.