Per costruire un grafo divisoriale, si fissi anzitutto un numero intero n, detto indice del grafo. I vertici del grafo sono allora i numeri interi da 1 a n. Nel grafo, uno spigolo collega due interi distinti se il maggiore è un multiplo del minore, o, equivalentemente, se il minore divide il maggiore. Per esempio, nel grafo divisoriale di indice n = 6, raffigurato qui sotto, si contano 6 vertici; il vertice 1 è collegato a tutti gli altri, il vertice 2 a 1, 4 e 6, il vertice 3 soltanto a 1 e 6, e così si ottengono tutti gli spigoli (gli spigoli che collegano 4 a 1, 4 a 2, 5 a 1, 6 a 1 e 6 a 3 sono già tracciati).
Grafo divisoriale di indice 6.
Si osservano subito alcune proprietà: il vertice 1 è collegato a tutti gli altri vertici; un vertice corrispondente a un numero primo è collegato soltanto ai suoi multipli e a 1, quindi a pochi vertici; al contrario, un intero con molti divisori è collegato a numerosi vertici.
Queste osservazioni possono dare un’idea della struttura del grafo divisoriale, ma essa resta difficile da cogliere e dunque da analizzare quando l’intero n scelto inizialmente diventa grande. Nel disegno qui sopra, il grafo divisoriale di indice 100 appare piuttosto confuso, anche se la sua rappresentazione «circolare» lascia già intravedere qualche motivo intrigante. Per valori di n sensibilmente maggiori, è illusorio sperare di comprendere il grafo a partire da uno dei suoi disegni.
