BrainDen.com - Brain Teasers
• 0

# points in a plane

Go to solution Solved by BMAD,

## Question

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?

## Recommended Posts

• 0

to be clear, for edges, i mean straight line segments and the plane is 2d.

##### Share on other sites
• 0

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.

##### Share on other sites
• 0

The best solution I can get is 2n for 6, and 2n + 1 for everything else. Put a polyhedron inside of another polyhedron.

##### Share on other sites
• 0
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.

I played with your solution.  Is there a condition missing?  It doesn't seem to hold for small n.

##### Share on other sites
• 1
• Solution

I have

Spoiler

when v > 2, edges = 3(vertex count) - 6

##### Share on other sites
• 0

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.

##### Share on other sites
• 0
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).

Grammar

## Join the conversation

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

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
• ### Recently Browsing   0 members

×

• #### Activity

• Riddles
×
• Create New...