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](https://en.wikipedia.org/wiki/Multipartite_graph).


It has been a while that I have investigated this problem and even proposed [an optimization task](https://lotfizadeh.org/wp-content/uploads/2021/12/Fuzzy-Graph.pdf) on that. You can also read [the solution](https://lotfizadeh.org/wp-content/uploads/2021/12/Fuzzy-Graph-Solution.pdf).


I would like to know if anyone has some proof or related work?



Maximum number of edges in a "coprime graph"
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.



```
0 [5, 6, 7, 9, 10, 11, 12] 7
1 [5, 6, 7, 9, 10, 11, 12] 7
2 [5, 6, 8, 9, 10, 11, 12] 7
3 [5, 7, 8, 9, 10, 11, 12] 7
4 [6, 7, 8, 9, 10, 11, 12] 7
5 [0, 1, 2, 3, 8, 9, 10, 11, 12] 9
6 [0, 1, 2, 4, 8, 9, 10, 11, 12] 9
7 [0, 1, 3, 4, 8, 9, 10, 11, 12] 9
8 [2, 3, 4, 5, 6, 7, 11, 12] 8
9 [0, 1, 2, 3, 4, 5, 6, 7, 11, 12] 10
10 [0, 1, 2, 3, 4, 5, 6, 7, 11, 12] 10
11 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 11
12 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 11

```

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.



```
x = Graph("L?BvUo~~v}^~~}")

```

