A factor graph is a graph where each node is numbered and if x is a factor of y, then x and y are connected. A graph is planar if it can be drawn on paper with no lines crossing.

1) Create a planar factor graph with nodes numbered from 2 through 23.

2a) [easy] Show that no planar factor graph is possible with nodes numbered 2 through 32.
2b) [hard] Show that no planar factor graph is possible with nodes numbered 2 through 24.

3) If the nodes are numbered 1 though n, find the largest planar factor graph and prove that n+1 is impossible.

Tip: A finite graph is planar if and only if it does not contain as a subgraph either the complete graph K₅ or the complete bipartite graph K_3,3.

(In reply to Part 3 - K5 and K3,3 by Brian Smith)

2 does not divide 15 evenly. To be part of the K(3,3), the path must be direct.

Edited on August 18, 2021, 7:49 am

Posted by Charlie on 2021-08-18 07:46:12