Let's define a coprime graph as a simple graph (undirected graph without any self-loops or multiple-edges) in which for all edges $(𝑢, 𝑣)$, the property $\gcd(\mathrm{degree}_u, \mathrm{degree}_v) = 1$ is true (i.e., degrees of vertices $𝑢$ and $𝑣$ are coprime).
I conjecture that, such a graph with maximum number of edges (is always) can always be obtained as a $k$-partite complete graph.
It has been a while that I have investigated this problem and even proposed an optimization task on that. You can also read the solution.
I would like to know if anyone has some proof or related work?
Best Answer
OK, I can now confirm that even your modified conjecture is false, although the first counterexample has $13$ vertices.
First we need to know which complete $k$-partite graphs on $13$ vertices are coprime and how many edges they have. Both of these things can be determined directly from the sizes of the partite-sets. So for each partition of $13$ with parts $p_1,p_2,\ldots,p_k$ we need to have $n-p_i$ coprime to $n-p_j$ for all $i < j$. For each such partition the number of edges of the corresponding complete $k$-partite graph is $\sum_{i<j}p_ip_j$
In this case, the winner is $K_{3,4,6}$ which has 12+18+24 = 54 edges.
However, here is a nice $13$-vertex graph that is coprime but has $56$ edges.
Each line contains a vertex name (from $0$-$12$), then a list a neighbours of that vertex, then the degree of that vertex.
The vertices of each fixed degree must be independent sets, and it is easy to check that $\{0,1,2,3,4\}$, $\{5,6,7\}$, $\{9,10\}$ and $\{11,12\}$ are indeed independent.
Any edge involving a vertex of degree $7$, $9$ and $11$ automatically has ends of coprime degree because $7$, $9$ and $11$ are coprime to every other degree. So it is only an edge connecting a vertex of degree $8$ to one of degree $10$ that can prevent this graph from being coprime. And no such edge exists.
You can put this directly into SageMath to construct the graph.