Library / Bulgarian Spring Tournament /9 of 15

Bulgarian Spring Tournament

Combinatorics Difficulty 6.4 National Olympiad Prove it Bulgaria

A graph $G$ is called divisibility graph if the vertices can be assigned distinct positive integers such that between two vertices assigned $u, v$ there is an edge iff $\frac{u}{v}$ or $\frac{v}{u}$ is a positive integer. Show that for any positive integer $n$ and $0 \le e \le \frac{n(n-1)}{2}$ , there is a divisibility graph with $n$ vertices and $e$ edges.
(Danila Cherkashin)

Solution

We reason inductively on $n$ , not writing the number $1$ at any vertex. For $n=1$ the requested is clear, for $n=2$ an example with $e=1$ is $(2, 4)$ and an example with $e=0$ is $(2, 3)$ . For $n=3$ example with $e=0$ is $3, 5, 7$ , example with $e=1$ is $2, 4, 7$ , example with $e=2$ is $2, 4, 10$ , an example with $e=3$ is $2, 4, 8$ .
For $n \ge 4$ we have $n-1 \le \frac{(n-1)(n-2)}{2}$ , so at least one of $e \ge n-1$ and $e \le \frac{(n-1)(n-2)}{2}$ is satisfied.
Let $e \ge n-1$ first. In an example with $n-1$ vertices and $e - (n-1)$ edges, we add a vertex (of degree $n-1$ ) by writing in it a prime number $p$ greater than the numbers in the other vertices, then we multiply the numbers in the remaining vertices by $p$ – this does not spawn new edges between the remaining vertices.
Now let $e \le \frac{(n-1)(n-2)}{2}$ . In an example with $n-1$ vertices and $e$ edges, we add a vertex (of degree $0$ ), writing in it a prime number $p$ greater than the numbers in the other vertices, and do not change the numbers in the other vertices – it does not spawn new edges.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.