A solution of problem related to planar graph

Question

I need an approaching method theoretically to solve the below problem.

4. (6pts.) For n ≥ 1 let G_n be the simple graph with vertex set V(G_n) = {1, 2, ..., n} in which two different vertices i and j are adjacent whenever j is a multiple of i or i is a multiple of j. For what n is G_n planar?

Answer 1

• Vertex 1 is adjacent to every other vertex (since any j is a multiple of 1).
• Vertex 2 is adjacent to Vertices 1, 4, 6, 8, ...
• Vertex 3 is adjacent to Vertices 1, 6, 9, 12, ...
• Vertex 4 is adjacent to Vertices 1, 2, 8, 12, 16, ...
• etc.

Each vertex is adjacent to other vertices that are factors or multiples of its index.

A graph is non-planar if it contains a K₅ or K_(3,3) minor therefore the problem reduces to what is the range of n values that does not contain one of those minors.

Forbidden Subgraphs

If you have a K_(3,3) graph with the lowest vertices 1, 2, 4 in one sub-set of the complete bipartite graph then, for the vertices in the other sub-set to be adjacent they must be multiples of the lowest-common-multiple (LCM) of 1, 2 and 4 and the lowest possible (different) values are 8, 12 and 16. If you put any other values in the first sub-set then the LCM will be higher and so the maximum value will be higher; therefore 16 is the lowest possible n that will contain a K_(3,3) subgraph.

If you have a K₅ graph and start with vertex 1 (2⁰) then the next lowest vertex it can connect to is vertex 2 (2¹) and the next lowest vertex that both can connect to is a multiple of both previous vertex indices and the lowest would be vertex 4 (2²) and, following the same logic, the final vertices would be 8 (2³) and 16 (2⁴).

Therefore the lowest n is 16 for both a K₅ subgraph and a K_(3,3) subgraph; giving the an initial bound on the range from 1 to 15.

---

Forbidden Minors

However, if you try to generate a planar embedding of a graph with 15 vertices you will find it is impossible.

This is because there is a K_(3,3) minor (that is not immediately obvious) with the vertices 1, 2, 3 in one sub-set and in the other sub-set vertices 6 and 12, which are both trivially adjacent to all the vertices of the first sub-set, and then if you collapse the edges (5,10) and (5,15) then the resultant collapsed vertex is also adjacent to all the vertices of the first sub-set (since 1 is adjacent to 5, 10 and 15, 2 is adjacent to 10 and 3 is adjacent to 15).

It is possible to generate a planar embedding of G₁₄:

Therefore, the Graphs with n from 1 to 14 have a planar embedding but any larger graphs are non-planar.