Explore topic-wise InterviewSolutions in .

The correct answer is (B) not canonical

The explanation is: A DIFFERENT Cayley GRAPH will be given for each choice of a generating set. Hence, the Cayley graph is not canonical.

The CORRECT answer is (a) group theory

The BEST explanation: Modern PARTICLE physics EXISTS with group theory. Group theory can predict the existence of many elementary particles. Depending on different symmetries, the structure and behaviour of molecules and crystals can be defined.

Right ANSWER is (b) endomorphism ring

To elaborate: We know that in basic ring theory, any ring R with its IDENTITY can be embedded in its own endomorphism ring and this is ONE of the most important characterization of rings. The endomorphism ring can contain a copy of its ring.

Correct CHOICE is (a) quasi group

For explanation: We know that any group is a REPRESENTATION of a GRAPH. Now, a Quasi Group can be represented by a LATIN Square matrix or by a Latin Square graph.

Right ANSWER is (a) homomorphism

Easy explanation: We know that there exists an isomorphism between group homology and group COHOMOLOGY of finite group. Let S’ denote the set of all integers, and let G’ be a finite cyclic Group and for EVERY S then G’-MODULE N, we have S’S’n(G’, A) is isomorphic to S’n+1(G’, A).

The correct option is (a) same as MANIFOLD

Easy explanation: If a GROUP is a (topological) manifold, then the dimension of a group will be the dimension of this manifold.A linear representation F of a group G1 on a VECTOR SPACE V’ has the dimension of V’.

Correct ANSWER is (C) a COUNTABLE group

The explanation: We know that any countable group can always be EMBEDDED in an ALGEBRAICALLY closed group.

Correct ANSWER is (a) commutation

The best explanation: Some generators of group G1 in group theory which goes EITHER into itself or zero under commutation with any other ELEMENT of the WHOLE algebra is called invariant subalgebra.

Right option is (B) a factorization via subgroups of G

Explanation: A DIRECT product of a GROUP G is a factorization via subgroups of G when the intersection is nontrivial, say X and Y, such that G = XY, X intersect Y = 1, and [X, Y]=1 and X, Y are normal in G.

The CORRECT choice is (b) subgraph

The BEST explanation: A non-planar graph can have removed EDGES and vertices so that it CONTAINS subgraphs. However, non-planar graphs cannot be DRAWN in a plane and so no edge of the graph can cross it.

The CORRECT OPTION is (b) 6

To explain: The plane graph with an edge at most 6+2(m−3) is the GREATEST PLANAR graph. So, in this CASE the number of edges is 6.

Correct CHOICE is (b) m≤5/3(n−2)

The best explanation: Because G is connected and planar, Euler’s theorem is BOUND to be involved. Let f denote the number of faces so that n−m+f=2. Because the length of the SMALLEST cycle in G is 5, every FACE has at least 5 edges adjacent to it. This means 2m≥5f because every edge is adjacent to two faces. Plugging this in yields 2=n−m+f≤n−m+2/5m=n−3/5m, and HENCE m≤5/3(n−2).

The CORRECT choice is (b) 9

The BEST explanation: Note that K3,3 and K5 are the “smallest” non-planar GRAPHS because in that every non-planar graph contains them. ACCORDING to Kuratowski’s THEOREM, a graph is defined as non-planar if and only if it contains a subgraph homomorphic to K3,3 or K5.

The correct answer is (a) 22/21

The explanation: The density of a planar graph or network is described as the ratio of the number of EDGES(E) to the number of POSSIBLE edges in a network with(N) nodes. So,D = E − N + 1/ 2 N − 5. Hence, the required answer is: D=(34-13+1)/(2*13-5) = 22/21. A completely sparse planar graph has density 0 and a completely DENSE planar graph has degree 1.

The correct answer is (d) 56

The explanation is: The CHROMATIC POLYNOMIAL PG of a graph G is a polynomial in which every natural number k returns the number PG(k) of k-colorings of G. Since, the DEGREE of PG is EQUAL to the number of VERTICES of G, the required answer is 56.

The correct answer is (c) 3

The explanation: Here n is odd and X(Cn)! = 2. Since there are two adjacent edges in Cn. Now, a graph coloring for Cn exists where VERTICES are COLORED red and blue alternatively and another edge is with a different colour SAY orange, then the value of X(Cn) becomes 3.

Right choice is (a) BFS

Best explanation: In BFS due to the least number of edges between TWO vertices and so if all the edges in a GRAPH are of same weight, then to find the shortest path BFS can be used for efficiency. So we have to split all edges of weight 5 into two edges of weight 2 each and one EDGE of weight 1. In the worst CASE, all edges are of weight 1. To split all edges, O(E) operations can be done and so the TIME complexity becomes which is equal to O(V+E).

Correct choice is (a) n-colorable

The EXPLANATION is: The chromatic number of a graph is the MINIMAL number of COLORS for which a graph coloring is possible. A graph G is termed as K-colorable if there EXISTS a graph coloring on G with k colors. If a graph is k-colorable, then it is n-colorable for any n>k.

The correct CHOICE is (b) graph ordering

The explanation: A graph coloring is an assignment of labels to the vertices of a graph such that no two adjacent vertices SHARE the same labels is called the COLORS of the graph. Now, the chromatic number of any graph is the minimal number of colors for which such an assignment is POSSIBLE.

Right answer is (a) complete graph

The best I can EXPLAIN: Suppose, the complement G’ of a graph G is known as edge-complement graph which consists of with the same vertex SET but whose edge set CONTAINS the edges not present in G. The graph sum G+G’ on an n-node graph G is called the complete graph SAY, KN.

The correct answer is (c) 78

Explanation: LET, an n-path COMPLEMENT graph Pn’ is the graph complement of the path graph Pn. Since Pn is self-complementary, P4’is isomorphic to P4. Now, Pn’ has an EDGE COUNT = ^1⁄2(n-2)(n-1). So, the required edge count is=78.

Right option is (b) Hamiltonian path

For explanation: The Eulerian path in a graph say, G is a walk from one vertex to ANOTHER, that can pass through all VERTICES of G as well as traverses exactly once every edge of G. Therefore, an Eulerian path can not be a CIRCUIT. A Hamiltonian path is a walk that contains every vertex of the graph exactly once. Hence, a Hamiltonian path is not a circuit.

Right choice is (a) cycle GRAPH

For explanation I would SAY: In the graph ncfkedn, no edges are repeated in the WALK, which makes it a TRAIL and then start and end vertex n is same MAKING it a cycle graph.

Right OPTION is (a) a walk without REPEATED EDGES

The explanation: SUPPOSE in a graph G a trail could be defined as a walk with no repeated edges. Suppose a walk can be defined as efgh. There are no repeated edges so this walk is a trail.

Right answer is (a) v0=vk

Explanation: A walk in a graph is said to be CLOSED if the STARTING vertex is the same as the ENDING vertex, that is v0=vk, it is described as Open otherwise.

Right CHOICE is (d) eulerian circuit

The best EXPLANATION: we know that he Eulerian circuit in a graph G is a circuit that includes all vertices and edges of G. A graph that can have Eulerian circuit, ALSO can have a Eulerian graph.

The CORRECT choice is (b) f(u) and f(V) are adjacent in H

To elaborate: Two graphs G and H are said to be isomorphic to each other if there exist a one to one CORRESPONDENCE, say f between the vertex sets V(G) and V(H) and aone to one correspondence g between the edge sets E(G) and E(H)with the following conditions:-

(i) for EVERY vertex u in G, there exists a vertex u’ in H such that u’=f(u) and vice versa.

(II) for every edge uv in G, g(uv)=f(u)*f(v)=u’v’ is H.

The correct OPTION is (b) planar GRAPH

To EXPLAIN I WOULD say: A graph is known as planar graph if and only if it does not CONTAIN a subgraph homeomorphic to k5 or k3,3.

The CORRECT choice is (c) n ≤ 4

Easy explanation: Any graph with 4 or LESS vertices is planar, any graph with 8 or less edges is planar and a complete n-node graph Kn is planar if and only if n ≤ 4.

The correct choice is (b) Polyhedral graph

The best I can EXPLAIN: A simple CONNECTED planar graph is called a polyhedral graph if the degree of each vertex is(V) ≥ 3 such that DEG(V) ≥ 3 ∀ V ∈ G and two conditions must SATISFY i) 3|V| ≤ 2|E| and ii) 3|R| ≤ 2|E|.

The correct OPTION is (b) 945

For EXPLANATION: Perfect matching is a set of edges such that each vertex APPEARS only once and all vertices appear at least once (exactly ONE appearance). So for n vertices perfect matching will have n/2 edges and there won’t be any perfect matching if n is odd. For n=10, we can choose the first edge in ^10C2 = 45 ways, second in ^8C2=28 ways, third in ^6C2=15 ways and so on. So, the total number of ways 45*28*15*6*1=113400. But perfect matching being a set, order of elements is not important and the permutations 5! of the 5 edges are same only. So, total number of perfect matching is 113400/5! = 945.

The correct answer is (c) k, k+2

To EXPLAIN I would say: By using invariant of isomorphism and property of EDGES of graph and its complement, we have: a) number of edges of isomorphic graphs must be the same.

b) number of edge of a graph + number of edges of complementary graph = Number of edges in Kn(complete graph), where n is the number of VERTICES in each of the 2 graphs which will be the same. So we KNOW number of edges in Kn =n(n-1)/2. So number of edges of each of the above 2 graph(a graph and its complement)=n(n-1)/4. So this means the number of vertices in each of the 2 graphs should be of the form “4x” or “4x+1” for integral value of number of edges which is necessary. Hence the required answer is 4x or 4x+1 so that on doing modulo we get 0 which is the definition of congruence.

Correct option is (d) adjacency matrix

To explain: A graph can exist in different forms having the same NUMBER of vertices, EDGES and also the same edge connectivity, such graphs are called ISOMORPHIC graphs. Two graphs G1 and G2 are SAID to be isomorphic if −> 1) their number of components (vertices and edges) are same and 2) their edge connectivity is retained. Isomorphic graphs must have adjacency matrix REPRESENTATION.

Right option is (d) k-1 and v-1

Explanation: If a VERTEX is REMOVED from the graph, lower bound: number of components DECREASED by one = k-1 (remove an isolated vertex which was a COMPONENT) and upper bound: number of components = v-1 (CONSIDER a vertex connected to all other vertices in a component as in a star and all other vertices outside this component being isolated. Now, removing the considered vertex makes all other (v-1) vertices isolated making (v-1) components.

Right CHOICE is (c) 18

For explanation I WOULD say: We know that, sum of degree of all the vertices = 2 * number of edges

2*7 + 5*2 + 6*x = 39*2

x=9

Number of vertices = 7 + 2 + 9 = 18.

The CORRECT option is (a) k-1

The explanation is: This is possible with SPANNING trees SINCE, a spanning tree with k nodes has k – 1 EDGES.

The CORRECT choice is (b) n

To explain I WOULD say: For making a cyclic graph, the minimum NUMBER of edges have to be EQUAL to the number of vertices. SO, the answer should be n minimum edges.

The correct answer is (c) 28

Easy explanation: In a graph of N VERTICES we can draw an EDGE from a vertex to n-1 vertex we will do it for n vertices and so TOTAL number of edges is n*(n-1). Now each edge is counted twice so the REQUIRED maximum number of edges is n*(n-1)/2. Hence, 8*(8-1)/2 = 28 edges.

Right answer is (c) 6

Easiest explanation: Edge SET consists of edges from i to J USING either 1) j = i+1 OR 2) j=3i. The trick to solving this question is to think in a reverse way. INSTEAD of finding a path from 1 to 50, try to find a path from 100 to 1. The edge sequence with the minimum number of edges is 1 – 3 – 9 – 10 – 11 – 33 which consists of 6 edges.

Right CHOICE is (b) 1/50

Explanation: For the given condition we can simply design a K-Map and mark an EDGE between every two adjacent cells in K-map. Hence, that will give us a Bipartite graph and CHROMATIC number for this = 2. Hence the ratio is 2/n=2/100=1/50 and the given graph is actually a hypercube graph.

The CORRECT choice is (d) Euler graph

The best I can explain: In any simple undirected graph, total degree of all VERTICES is even (since each edge contributes 2 degrees). So NUMBER of vertices having ODD degrees must be even, otherwise, their sum would have been odd, making total degree also odd. Now single vertex n is connected to all these even number of vertices (which have odd degrees). So, degree of n is also even. Moreover, now degree of all vertices which are connected to v is increased by 1, HENCE earlier vertices which had odd degree now have even degree. So now, all vertices in the graph have even degree, which is necessary and sufficient condition for euler graph.

Right CHOICE is (b) tree

Easy explanation: If all the edge weights of an UNDIRECTED graph are positive, any subset of edges that CONNECTS all the vertices and has minimum TOTAL weight is termed as a tree. In this case, we need to have a minimum spanning tree need to be EXACT.

Right option is (a) a simple cycle

To EXPLAIN I would say: In a CONNECTED graph, a bridge is an edge WHOSE REMOVAL disconnects the graph. In a cycle if we remove an edge, it will still be connected. So, bridge cannot be PART of a cycle. A clique is any complete subgraph of a graph.

Correct choice is (c) 184

Explanation: In a COMPLETE graph which is (N-1) regular (where n is the number of vertices) has edges n*(n-1)/2. In the graph n vertices are ADJACENT to n-1 vertices and an edge contributes two degree so dividing by 2. Hence, in a d regular graph number of edges will be n*d/2 = 46*8/2 = 184.