A coprime graph is a graph defined by making two objects adjacent when a pair of associated positive integers is relatively prime. The term is not completely standardized, and the associated integers depend on context.
A common number-theoretic version, the coprime graph of integers, has vertices 1, 2, ..., 
,
with two distinct vertices 
and 
adjacent iff 
, i.e., iff 
and 
are relatively prime (Erdős
and Sárközy 1997, Sárközy 1999, Sander and Sander 2009, Banerjee
2026). This graph is denoted 
by Banerjee (2026), while the House of Graphs database
uses labels such as 
for the corresponding graph on seven vertices.
Every coprime graph of integers is a traceable graph: for 
this is immediate, while for 
the vertex sequence 1, 2, ..., 
gives a Hamiltonian path,
since consecutive integers are relatively
prime. For 
,
the additional edge joining 
to 1 closes this path to a Hamiltonian cycle, since 
. The case 
is the Hamiltonian graph 
, while 
is nonhamiltonian; hence 
is the only nonhamiltonian coprime graph of integers.
Direct computation of the stable coloring produced by color refinement shows
that 
is amenable, and hence has Weisfeiler-Leman
dimension 1, for 
and again for 
.
For 
,
it is not amenable, so its Weisfeiler-Leman
dimension is greater than 1. Thus amenability
is not monotone in 
for this graph family.
At 
, the stable cells 
, 
, and 
are pairwise anisotropically related and form a triangle
graph in the anisotropic cell graph. This violates
the forest condition in the exact characterization of
amenable graphs (Arvind et al. 2017) and
certifies that 
is not amenable.
The named instances among small coprime graphs of integers are summarized in the following table.
A shifted integer variant, the 
-coprime graph of order 
, has vertex
set 
and the same relative-primality adjacency rule
(Bani Mostafa and Ghorbani 2021).
This adjacency convention is complementary to that used for an Erdős graph, whose Erdős sequence gives associated integers that make two vertices adjacent when the corresponding integers are not relatively prime.
In group theory, Ma, Wei, and Yang (2014) define the coprime graph of a finite group 
to have vertex set 
, with distinct elements 
and 
adjacent iff 
, where 
denotes the order of 
. This usage is also followed, for example,
for groups of integers modulo
and their subgroups
by Juliana et al. (2020). A related but different subgroup
version has as vertices the proper
subgroups of a group, with two vertices adjacent iff the corresponding
subgroup orders are relatively prime (Rajkumar and Devi 2015). Yet another
variant, the prime coprime graph of a finite group,
joins two group elements when 
is either 1 or a prime
(Banerjee and Adhikari 2022).
Thus, when the phrase "coprime graph" is used without qualification, the intended vertex set and the integers whose coprimality is being tested should be specified.
Group and Its Subgroups." J. Fundamental Math. Appl. 3,
15-18, 2020.