Kn,n,n be a complete 3-bipartite graph whose maximal independent setsare C1 = [n],C2 = [2n] – [n], and C3 = [3n] – [2n].-(a) How many edges does Kn,n,n have?(b) Does Kn,n,n have an Eulerian cycle?(c) Show by any means that Kn,n,n has a Hamilton cycle.(d) Let G be the graph that is obtained from Kn,n,n by removing theedges of your Hamilton cycle. Does G have an Eulerian cycle?

Answer for sub question a: To find the number of edges in Kn,n,n: First count the number of edges adjacent to a given vertex say vi: Since the given graph is a Kn,n,n 3-bipartite graph, the vertex vi will not be adjacent to n-1 vertices in the group to which it belongs and it will be adjacent to the remaining 2n vertices. Therefore number of edges incident on vi=2n. Total number of vertices in the graph=n3. Therefore number of edges incident on all the vertices =2n3n. But then, since each edge is incident on two vertices , each edge is counted twice. Therefore, total number of edges, =122n3n=3n2Answer for sub question b: Note: G contains a Eulerian cycle if and only if degree of each vertex of G is even. Since the degree of any vertex of the given graph is 2n, it follows that the given complete 3-bipartite graph Kn,n,n has a Eulerian cycle. Answer for sub question c: Note: If deg u + deg v≥n, where n is the total number of vertices in G, for each pair u,v of non adjacent vertices of G, then G is hamiltonian. Let u,v be a pair of non adjacent vertices of Kn,n,n. Then, degu+degv=2n+2n=4n Also, the number of vertices in Kn,n,n And clearly 4n>3n. Therefore it follows that G has a hamiltonian cycle.Answer for sub question d: Let G' be the graph obtained by removing the edges of the Hamiltonian cycle. When removing the edges of the Hamiltonian cycle degree of each vertex reduces by 2. Then the degree of each vertex in G' will be 2n-2, which is even. Therefore, it follows that the graph G' will have an Eulerian cycle.