All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Planar factor graphs (Posted on 2021-08-16) Difficulty: 3 of 5
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.

No Solution Yet Submitted by Jer    
Rating: 5.0000 (1 votes)

Comments: ( You must be logged in to post comments.)
  Subject Author Date
Some ThoughtsPart 3 - graphBrian Smith2021-08-19 12:41:48
re(4): Part 3 - K5 and K3,3Charlie2021-08-19 10:29:52
re(3): Part 3 - K5 and K3,3Charlie2021-08-19 06:55:43
re(2): Part 3 - K5 and K3,3Brian Smith2021-08-18 23:32:25
re: Part 3 - K5 and K3,3Charlie2021-08-18 17:54:04
re: Part 3 - K5 and K3,3Charlie2021-08-18 07:46:12
Some ThoughtsPart 3 - K5 and K3,3Brian Smith2021-08-17 23:11:01
re(2): Solution parts 1 and 2Brian Smith2021-08-17 22:46:04
re: 2b (therefore also 2a)Jer2021-08-17 22:11:58
re: Solution parts 1 and 2Jer2021-08-17 22:09:40
re: Solution parts 1 and 2Charlie2021-08-17 15:35:59
SolutionSolution parts 1 and 2Brian Smith2021-08-17 12:28:53
part 3 by computerCharlie2021-08-17 11:50:07
re: Setting an upper limit for 3Charlie2021-08-17 08:33:46
Setting an upper limit for 3Charlie2021-08-17 08:23:07
Some Thoughts2b (therefore also 2a)Charlie2021-08-16 20:55:45
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 (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information