# planar graph of Submultiples [duplicate]

This question already has an answer here:

There is Graph which is connected with Submultiples. (I am sorry but I don't know what this is called.)

For example,

10-node Graph has 10 nodes, 18 edges. node 1 connect all the other nodes. node 2 connect node number 2,4,6,8,10. node 3 connect 3,6,9. node 4 connect 4,8. etc. Image of Planar graph of 10-node Submultiple graph This is Planar graph of 10-node graph. ## Question 1.

It is easy to check if 11-node graph is planar or not. (Just put the node no.11 and connect with no.1) But, Is 12-node Submultiple graph planar? And how can I prove it? (I saw Kuratowski's theorem But I cannot find the graph of $$K_{3,3}$$ If there is, please show me with picture.

## Question 2.

If 12-node Submultiple graph is possible, How many node are possible? (I mean, 14 or 15 nodes graph is planar? or not?)

## marked as duplicate by saulspatz, Shailesh, Lord Shark the Unknown, YuiTo Cheng, CesareoMay 27 at 7:43

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• I think the word you're looking for is "divisors." – saulspatz May 26 at 21:45

## 1 Answer

Here is a planar graph for $$12$$ nodes: The thicker red edges are the onesthat I changed their orientations. Green edges are the ones that are incident to node $$12$$.

From here, I can say that for $$13$$ and $$14$$ nodes, it can be still planar. $$13$$ is similar to $$11$$ since $$13$$th node is just adjacent to $$1$$ and for $$14$$, we can add $$14$$ to outer face in which $$2$$ and $$7$$ reside.

For $$15$$, it is not trivial. But there is a $$K_{3,3}$$ subgraph using subdivions as the following: Then by Kuratowski's Theorem, it is not planar.

For $$16$$ nodes, I am sure that it cannot be planar because the nodes $$1,2,4,8,16$$ will all be connected to each other so we have $$K_5$$ as a subgraph. Then by Kuratowski's Theorem, it is not planar.