Graph theory

  • Thread starter jetoso
  • Start date
  • #1
73
0

Main Question or Discussion Point

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,565
3
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
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
1,356
2
label the nodes. and then show that there exists a spantree
 
  • #5
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,395
3
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.
 

Related Threads for: Graph theory

  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
10
Views
2K
  • Last Post
Replies
4
Views
7K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
3
Views
3K
Top