Consider a simple, undirected, and connected graph $G(V,E).$ In class, we saw that in order for

that graph to have an Eulerian cycle, it must have that all nodes have even degree. Answer the

following questions.

$($a$)$ First, assume that we can "double" an edge. That is$,$ we can duplicate it in the graph $($of

course, resulting in a graph that is no longer simple$).$ Consider, e$.$g$.,$ the following Figure $1$:

oubling of an edge in a

Should we double every edge, then is our graph definitely Eulerian? That is$,$ in any graph $G,$

if we double every edge in there, does the graph always have an Eulerian cycle? Either prove

this statement or provide a counter example to it$.$

$($b$)$ Recall the DNA sequencing problem we discussed during class and the Eulerian path problem

that was associated with it$.$ A bioinformatics group, motivated by the same lecture material,

decided to put this to the test. Alas, the graph they ended up with is not Eulerian. They believe

the issue to be with their DNA reads, which ended up being noisy and hence they lost exactly

one of the subsequences they should have obtained.

Recommend an algorithm for them to render the obtained graph Eulerian by adding

the necessary edge$($s$).$ For testing purposes, you can use your algorithm with the following

set of subsequences of $k=3,s$ :

$s=\{GGT,GTC,CCT,CTC,TCG,GCT,CGC,$CTA,TAA,AAC$\}$

The constructed network would be as in Figure $2$:

Figure $2$: The granh created with one missing subseauence.