1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Graph theory proof

  1. Jan 12, 2016 #1
    1. The problem statement, all variables and given/known data
    Let G be a connected graph. We say that G is minimally connected if the removal of any edge of G (without deleting any vertices) results in a disconnected graph. (a) Show that a connected, minimally connected graph has no cycles. (b) Show that a connected graph with no cycles is minimally connected. Commentary: The exercise shows that the two conditions are equivalent. A graph satisfying either condition is a tree.

    2. Relevant equations


    3. The attempt at a solution
    I approach this by proving that a tree is a minimally connected graph
    Proof
    A graph G is a tree if and only if every two vertices of G are connected by one path.
    Let G be a tree, delete any edge.
    This deleted edge connected a pair of vertices V1V2 which implies that the only path between V1 and V2 was the deleted edge. This shows that there is no path from V1 to V2. Therefore, the graph becomes disconnected hence we can't get from any vertex to any vertex.

    The assignment states that G is minimally connected if the removal of any edge of G results in a disconnected graph. Based on the definition of a tree and the stated proof we can say that a tree is a minimally connected graph and therefore it will satisfy the two previous conditions.


    Is that right?
     
  2. jcsd
  3. Jan 12, 2016 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    No. The thing you are trying to prove involves cycles. Why doesn't your proof say anything
    about cycles?
     
    Last edited: Jan 12, 2016
  4. Jan 12, 2016 #3
    Hello, I thought I could show that by proving that minimally connected graphs are trees hence a tree doesn't have cycles. To show that it doesn't have cycles, I can state that there is just one path between the vertices hence if we take away one edge, it will cause the disconnection of graph. This indicates that this deleted edge is the only path between the vertices that it connects. Hence there is just one path between every pair of vertices, the graph has no cycles because if there is a cycle, then the vertices that the cycle contains may have more than 1 path between them. Does this work?
     
  5. Jan 12, 2016 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yes, but for a formal proof you need to state that in the form of a contrapositive.
     
  6. Jan 12, 2016 #5
    contrapositive how?
     
  7. Jan 13, 2016 #6
    To prove part (a), assume for a contradiction a minimally connected graph has a cycle. Do you see why this is wrong? Just remove an edge from the cycle.
     
  8. Jan 13, 2016 #7

    epenguin

    User Avatar
    Homework Helper
    Gold Member

    As this is the third question of this kind you have asked, I would like to ask which of the following is true?:

    a) the theorem it Is/was to you not a statement of the obvious

    b) it was perfectly obvious to you, but you have to, or think you have to go through this somewhat heavy rigmarole because that is what your prof requires, or you think he does?

    (Though, that said, it is useful to have realised the connection between minimally connected graphs and trees - in fact minimal connection is part of one of the several alternative definitions of a tree. So I guess that realisation is an advantage and a virtue. But you don't need to mention trees to simply prove the theorem.)
     
    Last edited: Jan 13, 2016
  9. Jan 16, 2016 #8
    so this is so far what I got

    proof by contradiction
    Assume a minimally connected graph G has a cycle. If we take away one edge from the cycle, the graph doesn't become disconnected because in a cycle, the vertices may have more than 1 path between them. This contradicts the definition of minimally connected graphs which states that if the graph is minimally connected, the removal of any edge of G results in a disconnected graph. Therefore, G has no cycles.
     
    Last edited: Jan 16, 2016
  10. Jan 17, 2016 #9
    so this is so far what I got

    proof by contradiction
    Assume a minimally connected graph G has a cycle. If we take away one edge from the cycle, the graph doesn't become disconnected because in a cycle, the vertices may have more than 1 path between them. This contradicts the definition of minimally connected graphs which states that if the graph is minimally connected, the removal of any edge of G results in a disconnected graph. Therefore, G has no cycles.
     
  11. Jan 17, 2016 #10

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    that fails for a couple of reasons.
    1. You only say 'may' have more than 1 path. So the vertices might not have more than one path between them?
    2. You need to consider connectivity of all vertices in the graph, not just those in the cycle.
    Having removed one edge from the cycle, you need to show that any two given vertices are still connected.
     
    Last edited: Jan 17, 2016
  12. Jan 17, 2016 #11
    I just joined a few minutes ago. I like this.
     
  13. Jan 18, 2016 #12
    hello haruspex, I am just wondering if the first issue can be fixed by deleting the word may and say it has more than.....
    I still need to work on the second issue. I am also wondering if I am abusing too much the physics forums.
     
  14. Jan 18, 2016 #13

    epenguin

    User Avatar
    Homework Helper
    Gold Member

    IMHO your proof is now more direct and to the point than previously. :approve:

    I think you could meet haruspex' quibble objection :oldbiggrin: quite easily with an appeal to definition, which you might even be able to work into word-tweaking of your existing sentences, otherwise just add one.
     
  15. Jan 18, 2016 #14

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Yes, my first point is easily fixed by deletion of a word, but I cannot accept that my second point was trivial.
    The part
    is arguing this chain:
    Removing one edge from a cycle in a graph leaves the cycle connected, therefore a graph with a cycle is connected.
    That is clearly a wrong step since it makes no use of the fact that the graph was connected before removal of the edge. It's not hard to plug the hole, but it needs to be done.
     
  16. Jan 18, 2016 #15
    Assume a minimally connected graph G has a cycle. If we take away one edge from the cycle, the graph doesn't become disconnected because in a cycle, the vertices have more than 1 path between them and the vertices which don't belong to any cycle are still linked to some vertex in a cycle because by definition, the graph is connected. This contradicts the definition of minimally connected graphs which states that if the graph is minimally connected, the removal of any edge of G results in a disconnected graph. Therefore, G has no cycles.
     
  17. Jan 18, 2016 #16
    A moment ago#15

    Assume a minimally connected graph G has a cycle. If we take away one edge from the cycle, the graph doesn't become disconnected because in a cycle, the vertices have more than 1 path between them and the vertices which don't belong to any cycle are still linked to some vertex in a cycle because by definition, the graph is connected. This contradicts the definition of minimally connected graphs which states that if the graph is minimally connected, the removal of any edge of G results in a disconnected graph. Therefore, G has no cycles.
     
  18. Jan 18, 2016 #17

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Better, but still a bit handwaving. You only know the graph was connected before removal of the edge, so how do you know a vertex outside the cycle is still connected to a vertex in (what was) the cycle?
    It would be much more convincing along these lines:
    Let u, v be any two vertices in G. Since G is connected, there is a path P from u to v. If the edge removed from the cycle is not in P they are still connected. If it is in P ....
    Can you construct a new path that connects them?
     
  19. Jan 19, 2016 #18
    if it is in P they are still connected because in a cycle there are 2 paths between every vertex???. How do I arrange that in my proof??. I still don't get how this leads to a contradiction. Two vertices remain connected, but how does this show that the whole graph remains connected?............................................................ Sorry I think I got you. This shows that any two vertices whether in or outside the cycle remain connected after the deletion of an edge in the cycle. Now I have the next issue, I now think that in a cycle there are just 2 paths between the vertices that it contains.
     
    Last edited: Jan 19, 2016
  20. Jan 19, 2016 #19

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Within the cycle, yes. Why is that a problem?
     
  21. Jan 19, 2016 #20
    I previously stated that in a cycle there are more than 1 path between every vertex.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Graph theory proof
  1. Graph Theory Proof (Replies: 1)

  2. Graph theory proof (Replies: 11)

  3. Graph theory proof (Replies: 4)

Loading...