1. Limited time only! Sign up for a free 30min personal 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

  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