Removing 200 Points on a Plane: Solving the Circular Answer

[quddusaliquddus]

hi ,
there are a thousand, nine hundred, and 98 points on a plane. Each of these points connect to exactly three others (in the plane). you can travel from any point to any other by transversing different vertices.

Is it possible to remove 200 of these points -no two of which are connected by a single vertice in a way that in the points and connections that are leftover after the deletion, any point may still be reached from a sequence of transversals.

Can anyone help with this question ...though I am not too good at maths - i have no idea about topologies!

 

[quddusaliquddus]

A possible solution to this might be to arrange all the points on the circumference of a circle, then we join all opposite points with a vertice and we would end up with all points having three connections. Now this allows for points to be removed with a resulting correlation of the number of points on circumference and the number of points removable without upsetting the fact that none of the points removed were connected with a single flight and the remaining points are tranversal from any point to any other: (someone else helped me with this...credit where credit's due).

The pattern i initially spotted is a little inconsistent...or I am making mistakes...in my case both these explanations are equally likely :D

Is someone out there good with topologies?

 

[matt grime]

This has nothing top do with topology, and is an exercise in combinatorial graph theory. I'm not sure your embedding in the circle will help as you've not considered all possible ways of connecting the points.

Think like this: we remove one point, consider one of the points it was connected to. There are now two edges coming out from that point. label the edges out a and b. consider all the points that a connects to and all the points that b connects to. a and b can not be removed by the rules.

 

[quddusaliquddus]

i'll try that out. thanks.

 

[quddusaliquddus]

i need help. i can't do it.

 

[matt grime]

I suspect that the answer is negative, though I can't think of a good reason off the top of my head one of the problems with these things is they often require some clever trick that doesn't apply anywhere else. I feel here that if you remove 200 points (and the correpsonding 600 edges) that you must disconnect the graph into two parts, cos that seems easier to prove than the other conclusion.

 

[quddusaliquddus]

hmmm. problem is I've been told that i have to 'show' that this can be done...im in deep trouble.

 

[matt grime]

Ok, I think I know how to solve this, but I've not checked the details.

Just take any 4 points x,y,z,w where x,y,z are the three points w connects to. We remove w. We must show still that x connects to y, y to z and z to x. Try doing that by considering the possibility that they aren't connected. You can now pick 199 completely distinct sets of 4 points like this and remove one from each, you then must demonstrate that you may remove one of the remaining two points (which is thankfully trivial).

 

[Janitor]

This has nothing to do with topology, and is an exercise in combinatorial graph theory.

I agree with the second part of Matt's statement. But is Matt implying that graph theory is not a branch of topology? Maybe he is not implying such a thing, I realize.

At any rate, I have a book in front of me right now called Introduction to Graph Theory. It says, "Graph theory is the oldest and most geometric branch of topology, making it a natural supplement to either a geometry or topology course."

 

[matt grime]

The point I am making is that this is in a tensor analysis and differential topology thread, and the solution I am guessing has nothing to do with the techniques of (algebraic or differential) topology. It is a question about discrete mathematics. The graph can be realized as a simplicial complex, but its connectedness or otherwise after alteration is a purely combinatorial proof albeit about a semi-topological concept such as connectedness. The point alse being that we need no physical realization either to prove or state the result. I know of few people who do graph theory who would claim to be doing topology, but that is perhaps because topology these days means algebraic or, at a push, differential topology. There is overlap in all these things and it makes often little sense to put in arbitrary boundaries, but knowledge of topology is completely useless here.

 

[Janitor]

Thanks for the clarification.

I had not even noticed that this thread is in TA&DG. I got here via "New posts."

Out of curiosity, what would be the best forum to post a knot theory question?

 

[matt grime]

Depends what kind of question. I'd suggest abstract algebra is the best compromise as there's no topology thread