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: Part 3 - K5 and K3,3 by Charlie)
So starting with all nodes 1-15 and their connections.
Apply edge deletion to every edge except (1,6), (2,6), (3,6), (1,12), (2,12), (3,12), (1,15), (3,15), (2,10), (10,5), and (5,15).
Then apply edge contraction to (2,10). Then (2,10) and (10,5) are reduced to (2,5).
Then apply edge contraction to (2,5) Then (2,5) and (5,15) are reduced to (2,15).
This leaves a set of 9 edges: (1,6), (2,6), (3,6), (1,12), (2,12), (3,12), (1,15), (2,15), and (3,15). This graph minor is a K3,3 graph.
re(2): Part 3 - K5 and K3,3
