MathDB

A simple graph is called "divisibility", if it's possible to put distinct numbers on its vertices such that there is an edge between two vertices if and only if number of one of its vertices is divisible by another one.
A simple graph is called "permutationary", if it's possible to put numbers

1,2,...,n

on its vertices and there is a permutation

\pi

such that there is an edge between vertices

i,j

if and only if

i>j

and

\pi(i)< \pi(j)

(it's not directed!)
Prove that a simple graph is permutationary if and only if its complement and itself are divisibility.
Proposed by Morteza Saghafian .

Problem Statement