Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this community
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?
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:
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:
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:
and conveniently, that number is one greater than 224, which is a multiple of 16 and has this divisor graph:
Thus, the two smallest consecutive numbers whose proper divisors form a non-planar graph are
224 and 225.
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
