BMAD 64 Posted March 16, 2016 Report Share Posted March 16, 2016 Suppose there are 6 points in a plane. What is the most amount of edges that could be used to connect the points (without overlapping)? What if there were 7 points? 8 points? n points? Quote Link to post Share on other sites

1 Solution BMAD 64 Posted March 29, 2016 Author Solution Report Share Posted March 29, 2016 I have Spoiler when v > 2, edges = 3(vertex count) - 6 Quote Link to post Share on other sites

0 BMAD 64 Posted March 16, 2016 Author Report Share Posted March 16, 2016 (edited) to be clear, for edges, i mean straight line segments and the plane is 2d. Edited March 16, 2016 by BMAD Quote Link to post Share on other sites

0 bonanova 84 Posted March 16, 2016 Report Share Posted March 16, 2016 Here's a quick response, that may be way off Spoiler Make a convex polygon out of (n-1) of the points, and put the nth point inside. The perimeter comprises (n-1) edges. The "spokes" comprise another (n-1) edges. So 2(n-1) is a lower bound. Now modify the polygon, making it star-like and connect every other point, adding Floor [(n-1)/2] edges. Final answer: Floor [5(n-1)/2] edges. Quote Link to post Share on other sites

0 I_only_signed_up_for_this 0 Posted March 21, 2016 Report Share Posted March 21, 2016 The best solution I can get is 2n for 6, and 2n + 1 for everything else. Put a polyhedron inside of another polyhedron. Quote Link to post Share on other sites

0 BMAD 64 Posted March 28, 2016 Author Report Share Posted March 28, 2016 On 3/16/2016 at 5:32 PM, bonanova said: Here's a quick response, that may be way off Reveal hidden contents Make a convex polygon out of (n-1) of the points, and put the nth point inside. The perimeter comprises (n-1) edges. The "spokes" comprise another (n-1) edges. So 2(n-1) is a lower bound. Now modify the polygon, making it star-like and connect every other point, adding Floor [(n-1)/2] edges. Final answer: Floor [5(n-1)/2] edges. I played with your solution. Is there a condition missing? It doesn't seem to hold for small n. Quote Link to post Share on other sites

0 bonanova 84 Posted April 2, 2016 Report Share Posted April 2, 2016 I think your formula is correct. Spoiler My formula is correct for 6 and 7 points, but is low for 8 and 9 points. For 9 points, my formula says 20, but I get 21 edges. For 8 points, my formula says 17 but I get 18. Your formula correctly gives 21 and 18. Do you have a proof? Spoiler A simple construction shows that adding a point to an already optimal layout always permits 3 additional edges. Quote Link to post Share on other sites

0 BMAD 64 Posted April 2, 2016 Author Report Share Posted April 2, 2016 (edited) 1 hour ago, bonanova said: Hide contents Do you have a proof? Hide contents A simple construction shows that adding a point to an already optimal layout always permits 3 additional edges. In optimal (most edges being used) form, every new point after the fourth one will only add three edges. Making a chart of vertices to edges, one can see a linear relationship of vertices to edges (if you exclude the 1 & 2 vertices options). Edited April 2, 2016 by BMAD Grammar Quote Link to post Share on other sites

## Question

## BMAD 64

Suppose there are 6 points in a plane. What is the most amount of edges that could be used to connect the points (without overlapping)? What if there were 7 points? 8 points? n points?

## Link to post

## Share on other sites

## 7 answers to this question

## Recommended Posts

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.