Share
Explore BrainMass

An edge of a graph "G" is a bridge of "G" If and only if there exist vertices "U" and "W" such that "e" is on every U - W path of "G".

1.) An edge of a graph "G" is a bridge of "G" If and only if there exist vertices "U"
and "W" such that "e" is on every U - W path of "G".

2.) A graph "G" of order atleast 3 is Non Separable if and only if there exist two
internally disjoint U - V paths for every two distinct vertices "U" and "V" of "G".

Solution Preview

Proof:
1. If an edge of a graph G is a bridge, then the removal of this edge will disconnect the graph.
"=>": If e is a bridge, then I remove e from the graph G, then G has at least two disconnected components. I select vertex U in one component and W in another component, then U and W are disconnected ...

$2.19