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

  1. Sep 20, 2005 #1
    I am having problems to prove this: Show that a graph G remains connected even after deleting an arc (i,j) iff arc (i,j) belongs to some cycle in G.
    Grapgh G = (N, A), N = set of points of nodes, and A = set of arcs; an arc is an edge from node i to a different node j from N.

    Any suggestions?
  2. jcsd
  3. Sep 20, 2005 #2


    User Avatar
    Science Advisor
    Homework Helper

    You've deleted arc(i,j) but arc(i,j) is part of a cycle, so can you see that there still exists a path from i to j?
  4. Sep 20, 2005 #3
    Yes, in fact there still is one path between them. But my problem is trying to find a formal proof to show the if condition and the only if condition as well.
  5. Sep 20, 2005 #4
    label the nodes. and then show that there exists a spantree
  6. Sep 20, 2005 #5
    Oh, do you mean that deleting one arc from a cycle implies that there is a subgraph such that it includes all the nodes of the original graph G and some of the arcs of it?
  7. Sep 21, 2005 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    If we delete the arc A that has end points x and y and it is still connected, then there is still a path from x to y, call it B, and tehn the union of A and B is...

    conversely, if there is a cycle C and we remove some edge from between x and y then it is still connected since the resulting graph is the union of the connected component containing x, the connected component containing y, and x and y are still connected by the complement ot the removed edge in the arc.

    connectivity is transitive: if r is connnected to s and s is connected to t then r is connected to t.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook