# Graph theory

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?

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?

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?