MENU
No registration required!
N points in a plane
10 posts
• Page 1 of 1
N points in a plane
by harry.petrone » Sun Mar 26, 2017 4:10 am
Find the maximum number of points in a plane for which, among any 3 of them, there is always one pair having a distance of 1.
- harry.petrone
- Posts: 8
- Joined: Sun Mar 26, 2017 4:07 am
- Reputation: 0
Re: N points in a plane
by harry.petrone » Sun Mar 26, 2017 4:16 am
This is probably graph theory but it is not my favorite subject 
I guess we start with unit circles where all the points of distance 1 lie.
Not sure what to do next.
I guess we start with unit circles where all the points of distance 1 lie.
Not sure what to do next.
- harry.petrone
- Posts: 8
- Joined: Sun Mar 26, 2017 4:07 am
- Reputation: 0
Re: N points in a plane
by Guest » Sun Mar 26, 2017 8:47 am
The answer is 7.
Probably the easiest way to go about it is to inductively (on the number of vertices) construct all edge minimal graphs (where an edge indicates the vertices are of distance 1).
On 1 vertex there is one graph (just the vertex itself).
On 2 vertices there is one graph (just the pair of vertices with no edge between them (remember we are looking for edge minimal graphs)).
On 3 vertices there is one graph (an edge together with an isolated vertex).
On 4 vertices there are two graphs, which we can deduce by building on the 3 vertex case. If we add an extra vertex there are only a few ways we could join it to the 3 vertex case:
a) No edges from the new vertex. This forces all the other edges to be present, resulting in the minimal graph which is a triangle together with an isolated vertex.
b) One edge, from the new vertex to the isolated vertex. We don't need to add any other edges to make this work, the graph of two separate edges is edge minimal.
c) One edge, from the new vertex to an end point of an edge. This forces the edge from the other end of the "3-vertex case edge" to the isolated vertex to be present, which means this graph contains case (b) so is not edge minimal.
d) two edges, one to the isolated vertex, the other to the end point of the existing edge. Not minimal because it contains case (b).
e) two edges, both to the end points of the existing edge. Not minimal contains case (a).
f) three edges. Not minimal contains case (a).
On 5 vertices there are two graphs. A triangle with an edge, and a pentagon. I'll leave the reasoning as an exercise for you to do.
On 6 vertices there are two graphs. One of them is two triangles, I'll leave the other one for you to find.
On 7 vertices there is one graph, and on 8 vertices there are no graphs, I'll leave these as an exercise for you to do.
Hope this helped,
R. Baber.
Probably the easiest way to go about it is to inductively (on the number of vertices) construct all edge minimal graphs (where an edge indicates the vertices are of distance 1).
On 1 vertex there is one graph (just the vertex itself).
On 2 vertices there is one graph (just the pair of vertices with no edge between them (remember we are looking for edge minimal graphs)).
On 3 vertices there is one graph (an edge together with an isolated vertex).
On 4 vertices there are two graphs, which we can deduce by building on the 3 vertex case. If we add an extra vertex there are only a few ways we could join it to the 3 vertex case:
a) No edges from the new vertex. This forces all the other edges to be present, resulting in the minimal graph which is a triangle together with an isolated vertex.
b) One edge, from the new vertex to the isolated vertex. We don't need to add any other edges to make this work, the graph of two separate edges is edge minimal.
c) One edge, from the new vertex to an end point of an edge. This forces the edge from the other end of the "3-vertex case edge" to the isolated vertex to be present, which means this graph contains case (b) so is not edge minimal.
d) two edges, one to the isolated vertex, the other to the end point of the existing edge. Not minimal because it contains case (b).
e) two edges, both to the end points of the existing edge. Not minimal contains case (a).
f) three edges. Not minimal contains case (a).
On 5 vertices there are two graphs. A triangle with an edge, and a pentagon. I'll leave the reasoning as an exercise for you to do.
On 6 vertices there are two graphs. One of them is two triangles, I'll leave the other one for you to find.
On 7 vertices there is one graph, and on 8 vertices there are no graphs, I'll leave these as an exercise for you to do.
Hope this helped,
R. Baber.
- Guest
Re: N points in a plane
by Guest » Sun Apr 02, 2017 8:20 am
Minimal is a mathematical term that indicates of all the things that can be compared with the object, nothing is smaller. See
http://math.stackexchange.com/questions ... nd-minimal
In our case, the objects are graphs (on a fixed number of vertices), the comparison operator is defined as subgraph inclusion. If graph A is a (strict) subgraph of graph B (i.e. A is just B but with some edges missing) then A is less than B, or equivalently, B is greater than A. If A is not a subgraph of B, and B is not a subgraph of A, we say that they are not comparable.
On three vertices there are three graphs that satisfy the problem's criteria:
a) The graph on three vertices and one edge between two of the vertices.
b) The graph on three vertices and two edges.
c) The graph on three vertices with all three edges present.
However, only (a) is edge minimal, it is a subgraph of (b) and (c). If we take any graph that satisfies the criteria and is edge minimal, then add edges (without breaking the condition that it is planar) we'll still end up with a graph satisfying the criteria. The edge minimal graph is the underlying thing that is satisfying the criteria.
By keeping track of just the edge minimal graphs we reduce the number of graphs we need to keep track of at each stage. For example on 4 vertices there are 6 graphs that work, but only 2 are edge minimal. On 5 vertices there are 8 graphs that work, but again only 2 are edge minimal. The problem is a lot more manageable when only looking for the edge minimal cases.
Hope this helped,
R. Baber.
http://math.stackexchange.com/questions ... nd-minimal
In our case, the objects are graphs (on a fixed number of vertices), the comparison operator is defined as subgraph inclusion. If graph A is a (strict) subgraph of graph B (i.e. A is just B but with some edges missing) then A is less than B, or equivalently, B is greater than A. If A is not a subgraph of B, and B is not a subgraph of A, we say that they are not comparable.
On three vertices there are three graphs that satisfy the problem's criteria:
a) The graph on three vertices and one edge between two of the vertices.
b) The graph on three vertices and two edges.
c) The graph on three vertices with all three edges present.
However, only (a) is edge minimal, it is a subgraph of (b) and (c). If we take any graph that satisfies the criteria and is edge minimal, then add edges (without breaking the condition that it is planar) we'll still end up with a graph satisfying the criteria. The edge minimal graph is the underlying thing that is satisfying the criteria.
By keeping track of just the edge minimal graphs we reduce the number of graphs we need to keep track of at each stage. For example on 4 vertices there are 6 graphs that work, but only 2 are edge minimal. On 5 vertices there are 8 graphs that work, but again only 2 are edge minimal. The problem is a lot more manageable when only looking for the edge minimal cases.
Hope this helped,
R. Baber.
- Guest
Re: N points in a plane
by Guest » Sun Apr 02, 2017 8:34 am
Another way of looking at it, is that the edge minimal examples are the "simplest" graphs that satisfy the criteria.
If I have a graph that satisfies the criteria but I can remove an edge and it still satisfies the criteria, then the graph I started with wasn't as simple as it could have been (it wasn't edge minimal: there was a simpler "smaller" subgraph that was inside it).
If I have a graph that satisfies the criteria but whatever edge I try removing always results in something that does not satisfy the criteria, then the graph is as simple as possible (it is edge minimal: there are no simpler "smaller" subgraphs inside it that work).
R. Baber.
If I have a graph that satisfies the criteria but I can remove an edge and it still satisfies the criteria, then the graph I started with wasn't as simple as it could have been (it wasn't edge minimal: there was a simpler "smaller" subgraph that was inside it).
If I have a graph that satisfies the criteria but whatever edge I try removing always results in something that does not satisfy the criteria, then the graph is as simple as possible (it is edge minimal: there are no simpler "smaller" subgraphs inside it that work).
R. Baber.
- Guest
Re: N points in a plane
by Guest » Sun Apr 02, 2017 12:27 pm
Sorry I made a minor mistake: there are only 7 graphs that work on 5 vertices.
R. Baber.
R. Baber.
- Guest
Re: N points in a plane
by Guest » Tue Apr 11, 2017 9:32 am
Guest wrote:The answer is 7.
Probably the easiest way to go about it is to inductively (on the number of vertices) construct all edge minimal graphs (where an edge indicates the vertices are of distance 1).
On 1 vertex there is one graph (just the vertex itself).
On 2 vertices there is one graph (just the pair of vertices with no edge between them (remember we are looking for edge minimal graphs)).
On 3 vertices there is one graph (an edge together with an isolated vertex).
On 4 vertices there are two graphs, which we can deduce by building on the 3 vertex case. If we add an extra vertex there are only a few ways we could join it to the 3 vertex case:
a) No edges from the new vertex. This forces all the other edges to be present, resulting in the minimal graph which is a triangle together with an isolated vertex.
b) One edge, from the new vertex to the isolated vertex. We don't need to add any other edges to make this work, the graph of two separate edges is edge minimal.
c) One edge, from the new vertex to an end point of an edge. This forces the edge from the other end of the "3-vertex case edge" to the isolated vertex to be present, which means this graph contains case (b) so is not edge minimal.
d) two edges, one to the isolated vertex, the other to the end point of the existing edge. Not minimal because it contains case (b).
e) two edges, both to the end points of the existing edge. Not minimal contains case (a).
f) three edges. Not minimal contains case (a).
On 5 vertices there are two graphs. A triangle with an edge, and a pentagon. I'll leave the reasoning as an exercise for you to do.
On 6 vertices there are two graphs. One of them is two triangles, I'll leave the other one for you to find.
On 7 vertices there is one graph, and on 8 vertices there are no graphs, I'll leave these as an exercise for you to do.
Hope this helped,
R. Baber.
Dear R. Baber, what is the graph with 7 vertices? And how do we deduce there are no graphs with 8 vertices?
- Guest
10 posts
• Page 1 of 1
Who is online
Users browsing this forum: No registered users and 1 guest