Question 84
A finite simple graph $G$ with $n$ vertices is called divisible if it is possible to assign to each vertex $s$ of $G$ a number $n_{s}$ so that two distinct vertices always have two distinct numbers and any two vertices $s$ and $s^{\prime}$ are joined by an edge if and only if $n_{s} \mid n_{s^{\prime}}$ or $n_{s^{\prime}} \mid n_{s}$.
A finite simple graph $G$ with $n$ vertices is called permutable if it is possible to number the vertices of $G$ from $1$ to $n$ and there exists a permutation $\sigma$ of $\{1, \ldots, n\}$ such that the vertices numbered $i$ and $j$ are joined by an edge if and only if $(i-j)(\sigma(i)-\sigma(j))\lt 0$.
Prove that a graph $G$ is permutable if and only if $G$ and its complement are divisible.
A finite simple graph $G$ with $n$ vertices is called permutable if it is possible to number the vertices of $G$ from $1$ to $n$ and there exists a permutation $\sigma$ of $\{1, \ldots, n\}$ such that the vertices numbered $i$ and $j$ are joined by an edge if and only if $(i-j)(\sigma(i)-\sigma(j))\lt 0$.
Prove that a graph $G$ is permutable if and only if $G$ and its complement are divisible.