4
$\begingroup$

The divisibility graph of a set of positive integers is the graph whose vertices are the integers, two of which are joined by an edge if one divides the other.

What is the smallest positive integer the divisibility graph of whose proper divisors is non-planar?

And the first two such consecutive integers?

$\endgroup$
1
6
$\begingroup$

A graph is non-planar

if and only if it contains the complete graph $K_5$ or the complete bipartite graph $K_{3,3}$ as a subgraph.
A divisor graph will contain $K_5$ as a subgraph if it contains a set of 5 numbers which are of the form $a, ab, abc, abcd, abcde$, where $b, c, d, e \neq 1$. In this case, all 5 numbers will be multiples/divisors of each other, and will therefore all be connected. The lowest such set of numbers is ${1, 2, 4, 8, 16}$, the divisor graph for 32:
divisor graph for 32
A divisor graph will contain $K_{3,3}$ as a subgraph if it contains a set of 6 numbers which are of the form $a, b, c, abc, abcd, abce$, where $a \neq b \neq c$ and $d \neq e \neq 1$. In this case, all three of $a, b, c$ will connect to all three of the other numbers, forming a bipartite graph. The lowest such set of numbers is ${1, 2, 3, 6, 12, 18}$, part of the divisor graph for 36:
divisor graph for 36

Therefore, the smallest positive integer with a non-planar proper divisor graph is

32.

Finding the first two consecutive integers with this property is more complicated, because

any number with a divisibility graph like this can be represented as $abcden$, provided the relationships above hold and $n > 1$ for $K_5$ graphs. Therefore, any number with at least five (not necessarily distinct) prime factors ($b, c, d, e, n$) will form a $K_5$ graph, and any number with at least four prime factors where at least two are distinct from the other two ($\{b, c\}, \{d, e\}$) will form a $K_{3,3}$ graph (note that these numbers don't necessarily have to be prime, but then the number has five prime factors anyway). We also know that at least one of these numbers must be odd in order for them to be consecutive, and in order for a number to be odd, it must have only odd factors.

It turns out that

the smallest number we can make with only odd factors using those criteria is $3^2 * 5^2 = 225$, which has this divisor graph:

divisor graph for 225
and conveniently, that number is one greater than 224, which is a multiple of 16 and has this divisor graph:
divisor graph for 224

Thus, the two smallest consecutive numbers whose proper divisors form a non-planar graph are

224 and 225.

$\endgroup$
1
  • 4
    $\begingroup$ Doesn't have to be those two subgraphs exactly, any subdivision of them would also work. $\endgroup$
    – Bass
    Nov 19 '21 at 0:38
2
$\begingroup$

Freddy Barrera, using SAGE, has determined all integers not greater than 1000 whose divisibility graph is non-planar:

32, 36, 48, 60, 64, 72, 80, 84, 90, 96, 100, 108, 112, 120, 126, 128, 132, 140, 144, 150, 156, 160, 162, 168, 176, 180, 192, 196, 198, 200, 204, 208, 210, 216, 220, 224, 225, 228, 234, 240, 243, 252, 256, 260, 264, 270, 272, 276, 280, 288, 294, 300, 304, 306, 308, 312, 315, 320, 324, 330, 336, 340, 342, 348, 350, 352, 360, 364, 368, 372, 378, 380, 384, 390, 392, 396, 400, 405, 408, 414, 416, 420, 432, 440, 441, 444, 448, 450, 456, 460, 462, 464, 468, 476, 480, 484, 486, 490, 492, 495, 496, 500, 504, 510, 512, 516, 520, 522, 525, 528, 532, 540, 544, 546, 550, 552, 558, 560, 564, 567, 570, 572, 576, 580, 585, 588, 592, 594, 600, 608, 612, 616, 620, 624, 630, 636, 640, 644, 648, 650, 656, 660, 666, 672, 675, 676, 680, 684, 688, 690, 693, 696, 700, 702, 704, 708, 714, 720, 726, 728, 729, 732, 735, 736, 738, 740, 744, 748, 750, 752, 756, 760, 765, 768, 770, 774, 780, 784, 792, 798, 800, 804, 810, 812, 816, 819, 820, 825, 828, 832, 836, 840, 846, 848, 850, 852, 855, 858, 860, 864, 868, 870, 876, 880, 882, 884, 888, 891, 896, 900, 910, 912, 918, 920, 924, 928, 930, 936, 940, 944, 945, 948, 950, 952, 954, 960, 966, 968, 972, 975, 976, 980, 984, 988, 990, 992, 996, 1000

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.