MathDB

A graph

G

is called

<span class='latex-italic'>divisibility graph</span>

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}

\frac{v} {u}

is a positive integer. Show that for any positive integer

n

and

0 \leq e \leq \frac{n(n-1)}{2}

, there is a

<span class='latex-italic'>divisibility graph</span>

with

n

vertices and

e

edges.
[hide=Remark on source of 10.3] It appears to be Kvant 2022 Issue 10 M2719, so it will not be posted; the same problem was also used as 9.4.

Problem Statement