Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Possible circlular answer

  1. Mar 31, 2004 #1
    hi :smile: ,
    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 :confused: ...though im not too good at maths :redface: - i have no idea about topologies! :smile:
     
  2. jcsd
  3. Mar 31, 2004 #2
    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 im making mistakes...in my case both these explanations are equally likely :D

    Is someone out there good with topologies?
     
  4. Mar 31, 2004 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  5. Mar 31, 2004 #4
    i'll try that out. thanks.
     
  6. Apr 3, 2004 #5
    i need help. i can't do it.
     
  7. Apr 3, 2004 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  8. Apr 3, 2004 #7
    hmmm. problem is i've been told that i have to 'show' that this can be done....im in deep trouble.
     
  9. Apr 3, 2004 #8

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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).
     
  10. Apr 3, 2004 #9

    Janitor

    User Avatar
    Science Advisor

    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."
     
  11. Apr 3, 2004 #10

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  12. Apr 3, 2004 #11

    Janitor

    User Avatar
    Science Advisor

    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?
     
  13. Apr 3, 2004 #12

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Depends what kind of question. I'd suggest abstract algebra is the best compromise as there's no topology thread
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?