finding an Eulerian tour of an Eulerian graph can be done in

polynomial time. For that, we use the Fleury's algorithm. The idea is to travel vertices

so that the graph formed by unvisited edges is always connected. A bridge in a connected

graph is an edge that is the only path between its two endpoints. The graph below does not

have a bridge $($there is more than one path between any pair of vertices$),$ but if we remove

edge $(1,2),$ for example, then $(2,4),(3,4),$ and $(1,3)$ would be all bridges.

Fleury's algorithm: Create a copy $G^{\text{'}}$ of the input graph $G.$ Start at vertex $1$ and

iteratively select the next unvisited edge from $G^{\text{'}}$ as follows. When at vertex $u,$ form a set

$U$ of neighbors of $u$ in $G^{\text{'}}$ so that the edge $(u,v)$ is not a bridge in $G^{\text{'}}.$ If $U$ is empty, then $u$

is only connected to one vertex $v$ in $G^{\text{'}}$ through a bridge. In this case, we travel from $u$ to $v$

and remove $(u,v)$ from $G^{\text{'}}.$ Otherwise, when $U$ is not empty, travel from $u$ to any vinU and

remove $(u,v)$ from $C^{\text{'}}.$ In this course, we assume we travel to vinU with minimum index.

For example, in the above graph, we start at vertex $1.$ Then $U$ is $\{(1,2),(1,3),(1,5),(1,7)\}.$

We then travel from $1$ to $2($because $2$ has a smaller index than other vertices in $U)$ and

remove $(1,2)$ from the graph. Now at $2,U$ will be empty is a bridge in the updated

$G^{\text{'}}).$ We then travel from $2$ to $4$ and remove $(2,4)$ from $G^{\text{'}}.$ We proceed similarly and get an

Eulcrian tour $1,2,4,3,1,5,6,7,1$

$($a$)$

$($b$)$

$($c$)$

$($d$)$

For each of the following graphs, write down the Eulerian tour given by Fleury's algorithm. Also, you dont have to show intermediate steps