1
$\begingroup$

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.

enter image description here

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?)

$\endgroup$

marked as duplicate by saulspatz, Shailesh, Lord Shark the Unknown, YuiTo Cheng, Cesareo May 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.

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

Here is a planar graph for $12$ nodes:

enter image description here

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:

enter image description here

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.