Euler Cycles
————————————
Motivation : Genome Assembly Program → Given a set S = 3-perm({A,T,C,G}, find a string s = w₁w₂..wᵣ, s.t., wᵢ ∈ S, ∀ wᵢ

Defⁿ: Given G = (V,E), an Eulerian Cycle E(G), is a cycle Cᵢ, s.t., |Cᵢ| = |E|

Thᵐ : Given G = (V,E), st, G is connected and undirected, ∃ E(G) ⇔ ∀ v ∈ V(G) , deg(v) = Even
Proof : We split it into 2 cases -
a) Given : G =(V,E), s.t., G has E(G)
Then, let's assume that ∃ v ∈ V(G) s.t., deg(v) = odd.
Clearly, when v is traversed in E(G), everytime it is "approached", it must be "left". However, the odd degree implies that there will be one edge that cannot
be traversed as a result of no unvisited edges that can be left from. Hence, ∃ edge e = (v, v'), s.t., e ∉ E(G). This is a contradiction. Therefore, deg(v) = Even

b) Given : G=(V,E) s.t., ∀ v ∈ V(G), dev(v) = Even
Pick some v ∈ V(G). Start on an outside Random Walk from this. Let w = v₁v₂..vᵢ, until you hit v₁ = vᵢ, and |w| < |E|. Then ∃ vᵢ' ∈ w, s.t., vᵢ' has an unexplored
out edge. Start a new walk and repeat this procedure. On intersecting vertices on walks wₐ and wⱼ, we can union the 2 cycles to create a new one. This way, when we
have fully explored all the edges, and unioned all intersecting walks, we end up with an Eulerian Cycle

QED

Note: An Eulerian Path Eⱼ(G) = v₁...vⱼ....vᵢ can be extended to an Eulerian Cycle E(G) = v₁...vⱼ...vᵢv₁, by making E = E ∪ {vᵢ,v₁}

→ Part b) of the proof the Thᵐ shows that ∃ an Efficient Algorithm A, s.t., A can compute the Eulerian Cycle of G

Hamiltonian Cycles
——————————————————
Motivation : Goal is to traverse the Graph and visit every vertex just once, not only every edge

Defⁿ: A simple Euler Cycle, i.e., H(G) = simple(E(G))

Thᵐ : Given G = (V,E), finding H(G) is NP-Complete

Genome Assembly
——————————————–
Construction : Hamiltonian Cycle over a Graph G = (V,E), where, V = (S = 3-perm{A,T,C,G}) ∧ E = {(vᵢ,vⱼ) | suffix(vᵢ) = 2-prefix(vⱼ)}
Solⁿ : Find a Hamiltonian Path over this graph setup → NP-Complete

Idea : See, if we can reduce the Genome Problem in Poly(|S|) time to a problem P, s.t., P ∉ NP-Complete
i) Try reducing to a De-Brujin Graph DBG, where, an edge represents a valid sᵢ ∈ S.
ii) So - ∀ sᵢ , sᵢ → (vᵢ,vⱼ), where vᵢ = 2-prefix(sᵢ) and vⱼ = 2-suffix(sⱼ)
iii) Now, in order to find a string s = w₁w₂....wᵢ , s.t., we simply construct an Eulerian Cycle.
a) wᵢ = perm(A,T,C,G), wⱼ = perm'(A,T,C,J)
b) word(wᵢwⱼ) = perm(A,T,C,G) ∪ perm'(A,T,C,G) = (vᵢ, vⱼ) ∈ E
c) By induction, as every edge represents one 3-perm, going over all edges represents a valid 3-perm string concatenation