Let G= (V, E) be an undirected graph. An edge e
The converse is not true (articulation points do not imply bridges) (an example is here why?)
However, I claim <x,y> = e is a bridge iff e is on no cycle of G. (1) Consider the validity of this statement (2) consider the algorithm
If <x,y> = e is a bridge (without loss of generality, suppose x is the parent of y on a DF traversal ( nondirected graph ) then I further claim DFN(y) = L(y) (this is important - it determines cycles). For visual verification remember Figure 6.9 and with DFN and lows. Also a new one Conveniently, the DFN and node number are the same here
With this information, we can use the algorithm in Horowitz which finds
Comment: the pop after the loop is to remove bridges between loops from Stack, i.e., has biconnected components
however, this is only a bridge for bridge connected components. The pop will get it out of the Stack.
Changes to Horowitz algorithm [ O(v+e) ] were merely a few more if statements to compare.
** I should initialize the stack to contain (0,1) to ensure there is always an edge to pop after loop.
An Euler partition of a graph G = (V, E) is a partition of E into a set of edge disjoint paths and circuits such that every node of odd degree is at the endpoint of exactly one path. Write an O(|V| + |E|) algorithm to compute the Euler partition.
Example: Observations: <x,y> = e is a bridge => x or y are articulation point(s) except for base case (only one edge)
but rather than getting the biconnected components, we shall find the bridge connected components (slight change to Horowitz code will result in loops or singleton vertices).
Algorithm ART2(u,v) // same comments as in book's ART(u,v) algorithm
// including initialization of global DNF to 0, num to 1, PARENT array, etc.
// initialize the stack to contain (0,1), see **
{ DFN(u) = num; L(u) = num; num = num + 1
PARENT(u) = v
for each vertex w adjacent from u do
if v != w and DFN(w) < DFN(u) then add (u, w) to top of Stack //endif
if DFN(w) = 0 then
{
call ART2(w,u) // w is unvisited
if L(w) > DFN(u) then
{
print ("new biconnected component")
delete an edge fromm top of Stack. Let this edge be (x,y)
if (x,y) = (u, w) or (x,y) = (w,u) then //first edge matches - should anyway
{
if BFN(y) = L(y) then
{
print (y) // singleton
print ("Bridge", "(", PARENT(y), ",", y , ")")
}
//endif
}
else
{
print ("(", x, ",", y , ")") //first in cycle
loop
delete an edge from top of Stack. Let this edge be (x,y)
print ("(", x, ",", y , ")")
until (((x,y)=(u,w) OR (x,y)=(w,u)) AND (BFN(y)=L(y)) )
pop next element of Stack - call it (x,y) //bridge connection for loop
print ("Bridge", "(", x, ",", y , ")")
}
// endif (x,y) = (u, w)
}
// endif L(w) > DFN(u)
L(u) = min(L(u),L(w))
}
else if w != v then L(u) = min (L(u), DFN(w)) //endif
// endif
repeat // for
}
Analysis of time complexity:
the time complexity thus remains the same.
(Span Tree O(v+e) traverse through and a calculation for each node O(v+e))
Also to ensure that 
will get components 1, 2, and 3
Assuming the problem is solvable (i.e., that there exists an Euler Partition), then all paths must start with an odd node - or become a loop. Capitalize on this...
