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 K5 or the complete bipartite graph K3,3.
(In reply to
re: Solution parts 1 and 2 by Jer)
Hmm, it seems I can connect 2 to 20 in my graph just by running another line parallel to the 20-4-16-8-2 chain.
I don't feel like hacking the ascii graph any further though just to illustrate that line. That 2 needs a LOT of connections.
My core was the 3-6-12-18-2 diamond in the middle, then the remaining even numbers sit on the right side and the other multiples of 3 sit on the left side.
re(2): Solution parts 1 and 2
