perplexus.info :: Just Math : Planar factor graphs

Planar factor graphs (Posted on 2021-08-16)

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.

No Solution Yet Submitted by Jer

Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)

Solution parts 1 and 2

| Comment 5 of 16 |

2a: The graph of {2,4,8,16,32} form K(5)

2b: The graph of {2,3,6} to {12,18,24} form K(3,3)

1: crude ascii graph

             /--------+
 13 19      20-----+  |
            |      |  |
 17 23  12--4-\    |  |
       / |\ | 16   |  |
      /  | \|/ |   |  |
 +---3---6--2--8   |  |
 |  /|\  | /|\\---10--5
 | | | \ | || \       |
 | | |  \|/ |  +--+   |
 | | 9--18  |     |   |
 | |       22-11  |   |
 | 21-----7------14   |
 |                    |
15--------------------+

Posted by Brian Smith on 2021-08-17 12:28:53

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (5)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info