Question 39
A simple graph is called **divisibility** if it's possible to label its vertices with positive integers such that there is an edge between two vertices if and only if the label of one vertex is divisible by the other one.
A simple graph is called a **permutation** graph, if it's possible to label its vertices by $1, 2, \dots, n$ and there exists a permutation $\pi$ such that there is an edge between vertices $i, j$ if and only if $i \gt j$ and $\pi(i) \lt \pi(j)$ (the graph is not directed!)
Prove that a simple graph is a permutation graph if and only if both its complement and itself are divisibility graphs.
A simple graph is called a **permutation** graph, if it's possible to label its vertices by $1, 2, \dots, n$ and there exists a permutation $\pi$ such that there is an edge between vertices $i, j$ if and only if $i \gt j$ and $\pi(i) \lt \pi(j)$ (the graph is not directed!)
Prove that a simple graph is a permutation graph if and only if both its complement and itself are divisibility graphs.