Define disjoint set and answer the following questions. i. Show that after all edges are processed by CONNECTED-COMPONENTS, two vertices are in the same connected component if and only if they are in the same set. ii. During the execution of CONNECTED-COMPONENTS on an undirected graph G(V,E) with k connected components, how many times is FIND-SET called? How many times is UNION called? Express your answers in terms of IVI, |E|, and k.

Explain Eulerian and Hamiltonian graphs with examples, also draw the graphs of the following:

i) Eulerian but not Hamiltonian

ii) Hamiltonian but not Eulerian

What is planner graph? Draw the planner graph of the given graph.

Define Handshaking Theorem/Lemma. Find the in-degree and out-degree of each vertex in the following graph with directed edges.