Consider graph G with vertices $1,2,3,$ and $4,$ and edges $12,$

$23,34,14,$ and $13.$

$($a$)$ Present graph G$.$

$($b$)$ Present the adjacency lists for G$.$

$($c$)$ Show the graph obtained from G by deleting the edge $13($i$.$e$.,$ the

new graph has one fewer edge than G$).$

$($d$)$ Present the adjacency lists of the graph in $($c$).$

$($e$)$ Suppose we are given graph G $($i$.$e$.$ its adjacency lists$)$ and vertices x$,$

y such that x $$ y is an edge in G $($i$.$e$.$ each of x$,$ y is a vertex from

$1$ n$).$

What is the complexity of deleting the edge x $$ y from G$?$ Explain.

$($f$)$ By a cycle passing through edge x$$y$,$ I mean a cycle whose edges include

x $$ y$.$ Length of a cycle is the number of edges on the cycle.

Suppose we are given graph G and vertices x$,$ y such that x $$ y is an

edge in G$.$ We want to find a shortest cycle that passes through the

edge x $$ y$.$

Present an O$($m $+$ n$)$ time algorithm for the problem.

In the event that there is no cycle passing through the edge x $$ y$,$

output an appropriate message.

Hint: Would it help to start by deleing the edge x $$ y$?$