Proving Graph G Connectivity After Removing Arc (i,j)

[jetoso]

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?

 

[AKG]

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?

 

[jetoso]

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.

 

[neurocomp2003]

label the nodes. and then show that there exists a spantree

 

[jetoso]

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?

 

[matt grime]

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.