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.
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 coprime (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.