How to solve difficult positive integers and co-prime word problem? This is a very interesting word problem that I came across in an old textbook of mine. So I know its got something to do with derivative of algebra and prime numbers, which yields the shortest, simplest proofs, but other than that, the textbook gave no hints really and I'm really not sure about how to approach it. Any guidance hints or help would be truly greatly appreciated. Thanks in advance :) So anyway, here the problem goes:

The Roads Department in the state of Graphium uses graphs consisting of dots (called vertices) that represent towns, and lines (called edges) that represent roads between towns. To keep track of things they label the vertices with consecutive positive integers so that if two towns are joined by a road, then the numbers on the corresponding vertices are coprime, that is, their only common factor is 1. Such a labelled graph is called a COP-graph. Note that if two twons do not have a road joining them, then their labels may or may not be coprime. Here are two examples of COP-graphs, one with labels 1 to 5, the other with labels 1-6.

a) Show that the labels on COP-graphs A and B could be replaced with the integers 2 to 6 and 2 to 7 respectively so they remain COP-graphs.
b) Explain why COP-graph B could not remain a COP-graph if its labels were replaced with integers 5-10.
c) Explain why COP-graph A remains a COP-graph no matter what set of five positive consecutive positive integers label the vertices.
d) If a COP-graph has six vertices and labels 1 to 6, what is the maximum numbers of edges it can have? Explain.
a) Just write down the integers 2 to 6 (or 2 to 7) and join every pair of coprimes by edges. You should be able to see the graphs $A$ and $B$ in the results.

b) Each of vertices (originally) labelled $1,2,4,5$ has three neighbours. Among $5,6,7,8,9,10$, the number $6$ is coprime only to $5,7$ and $10$ is coprime only to $7,9$; hence $5,7,8,9$  must be used in some order for $1,2,4,5$ and $6,10$ replace $3,6$. and the two coprimes each has must correspond to their nieighbours in $B$. However, then $6$ and $10$ must have the common neighbour $7$ - but there is no common neighbour in $B$.

c) For odd $n$ $$\begin{matrix}&amp;&amp;n+4\\n&amp;n+1&amp;n+2&amp;n+3\end{matrix} $$
works and for even $n$
$$\begin{matrix}&amp;&amp;n+2\\n&amp;n+1&amp;n+3&amp;n+4\end{matrix} $$
works

d) Join coprime numbers by an edge and count edges. Any valid graph must be a subgraph of this and hence has at most just as many edges.
d is 15 edges, c is because COP grah a has only one town with two coprime neighbours