Graph theory

  • Thread starter jetoso
  • Start date
  • #1
jetoso
73
0
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?
 

Answers and Replies

  • #2
AKG
Science Advisor
Homework Helper
2,566
4
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?
 
  • #3
jetoso
73
0
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.
 
  • #4
neurocomp2003
1,366
3
label the nodes. and then show that there exists a spantree
 
  • #5
jetoso
73
0
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?
 
  • #6
matt grime
Science Advisor
Homework Helper
9,426
4
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.
 

Suggested for: Graph theory

Replies
7
Views
2K
  • Last Post
Replies
17
Views
652
  • Last Post
Replies
1
Views
327
  • Last Post
Replies
2
Views
339
  • Last Post
Replies
1
Views
414
  • Last Post
Replies
17
Views
2K
Replies
23
Views
529
Replies
1
Views
1K
  • Last Post
Replies
2
Views
304
Top