Coprime Graph – Maximum Number of Edges

graph theorynt.number-theoryreference-request

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.

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}^~~}")
Related Question