Explore topic-wise InterviewSolutions in .

Correct answer is (B) m^n-1 * n^n-1

The best I can explain: Spanning TREE of a given graph is defined as the subgraph or the tree with all the given VERTICES but having minimum number of edges. So, there are a total of m^n-1 * n^n-1 spanning TREES for a complete bipartite graph.

The correct ANSWER is (a) True

For explanation: Yes, the modular graph in graph THEORY is defined as an UNDIRECTED graph in which all three VERTICES have at LEAST one median vertex. So all complete bipartite graph is called modular graph.

Right option is (d) N*m

Explanation: The LAPLACIAN matrix is used to represent a finite GRAPH in the mathematical field of Graph Theory. Therefore, the Eigen values for the complete BIPARTITE graph is found to be n + m, n, m, 0.

Right answer is (b) m-1

For explanation: The laplacian matrix is used to represent a finite graph in the MATHEMATICAL field of Graph Theory. The multiplicity of the laplacian matrix of COMPLETE BIPARTITE graph with EIGEN Value n is m-1.

The correct ANSWER is (a) True

The explanation is: In GRAPH theory, Moore graph is DEFINED as a REGULAR graph that has a degree d and DIAMETER k. therefore, every complete bipartite graph is a Moore Graph.

The correct OPTION is (c) K3, 2

Best explanation: Minor graph is formed by deleting CERTAIN number of edges from a graph or by deleting certain number off vertices from a graph. Hence Outer PLANAR graph cannot CONTAIN K3, 2 as a minor graph.

Correct choice is (d) nm

For explanation: The adjacency MATRIX is a square matrix that is used to represent a finite GRAPH. Therefore, the Eigen values for the complete BIPARTITE graph is found to be (nm)^1/2, (-nm)^1/2, 0.

The correct option is (a) Planar GRAPH

For explanation: Minor graph is formed by deleting certain number of EDGES from a graph or by deleting certain number off VERTICES from a graph. HENCE Planar graph cannot contain K3, 3 as a minor graph.

Correct CHOICE is (d) NP-Complete PROBLEM

To explain: NP stands for nondeterministic polynomial time. In a bipartite graph, the TESTING of a complete bipartite subgraph in a bipartite graph is an NP-Complete Problem.

Correct answer is (b) Claw Graph

For EXPLANATION: Star is a complete bipartite graph with one INTERNAL node and K leaves. Star with three edges is CALLED a claw. Hence this graph is USED to define claw free graph.

The correct ANSWER is (b) COMPLETE BIPARTITE

Easy explanation - A graph is KNOWN as complete bipartite graph if and only if it has all the vertex of FIRST set connected to all the vertex of second set. Complete Bipartite graph is also known as Biclique.

Correct choice is (b) Complete Bipartite

For explanation: The graph is known as Bipartite if the graph does not contain any ODD LENGTH cycle in it. The complete bipartite graph has all the vertex of first SET CONNECTED to all the vertex of SECOND set.

The CORRECT answer is (a) True

For explanation: Berge THEOREM proves the FORBIDDEN graph characterization of every perfect GRAPHS. Because of that REASON every bipartite graph is perfect graph.

The correct option is (B) False

For explanation: A graph is known as bipartite graph if and only if it has the TOTAL chromatic number less than or equal to 2. The smallest number of graphs needed to color the graph is the chromatic number. But the chromatic number cannot be NEGATIVE.

Correct choice is (c) 2

Explanation: The perfect bipartite graph has CLIQUE SIZE 2. So the clique size of COMPLIMENT of LINE Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph and EVERY Bipartite Graph is 2.

Right answer: (C) 2

The perfect bipartite GRAPH has CHROMATIC NUMBER 2. So the COMPLIMENT of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph and every Bipartite Graph has chromatic number 2.

Right ANSWER is (a) PERFECT graph

The best I can explain: The perfect bipartite graph has clique size 2. ALSO, the clique size of COMPLIMENT of LINE Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph and every Bipartite Graph is 2.

Correct choice is (d) LINE GRAPH

To explain: TThe COMPLIMENT of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph and EVERY Bipartite Graph is known as a perfect graph in graph theory. Normal line graph is not a perfect graph WHEREAS line perfect graph is a graph whose line graph is a perfect graph.

The CORRECT option is (a) Konig’s Theorem

Explanation: The Konig’s theorem given the EQUIVALENCE relation between the minimum vertex cover and the maximum matching in graph THEORY. BIPARTITE graph has a SIZE of minimum vertex cover equal to maximum matching.

Correct choice is (a) 1

The best I can explain: A graph is known as bipartite graph if and only if it has the total CHROMATIC number less than or equal to 2. The SMALLEST number of graphs NEEDED to COLOR the graph is the chromatic number.

Right option is (d) Asymmetric spectrum

Easiest explanation - A graph is known to be bipartite if it has ODD length cycle number. It also has symmetric spectrum and the bipartite graph CONTAINS the total CHROMATIC number less than or equal to 2.

Right option is (a) Symmetric

To EXPLAIN: The spectrum of the bipartite graph is symmetric in nature. The spectrum is the property of graph that are related to polynomial, Eigen VALUES, Eigen VECTORS of the matrix related to graph.

Right answer is (B) Bipartite

Explanation: A GRAPH is known as bipartite graph if and only if it has the total chromatic number less than or equal to 2. The smallest number of GRAPHS needed to COLOR the graph is chromatic number.

Right OPTION is (a) BIPARTITE

For EXPLANATION: The GRAPH is known as Bipartite if the graph does not contain any odd length cycle in it. Odd length cycle MEANS a cycle with the odd number of vertices in it.

Correct option is (b) The given graph is bipartite

The best I can explain: A graph is said to be colorable if two vertices connected by an EDGE are never of the same COLOR. 2 colorable MEAN that this can be ACHIEVED with just 2 COLORS.

Right choice is (a) Yes

For explanation: If a graph is such that there exists a path which visits every EDGE ATLEAST once, then it is said to be EULERIAN. Taking an example of a square, the GIVEN question EVALUATES to yes.

Correct OPTION is (a) Yes

Explanation: It is REQUIRED that the graph is CONNECTED also. If it is not then it cannot be CALLED a bipartite graph.

Correct CHOICE is (a) 100

To explain: Let the given bipartition X have x vertices, then Y will have 20-x vertices. We NEED to MAXIMIZE x*(20-x). This will be maxed when x=10.

Right CHOICE is (a) Yes

For EXPLANATION: Condition NEEDED is that there should not be an odd cycle. But in a tree there are no CYCLES at all. Hence it is bipartite.

The correct choice is (a) If it can be DIVIDED into two independent SETS A and B such that each edge CONNECTS a vertex from to A to B

For EXPLANATION: A graph is said to be bipartite if it can be divided into two independent sets A and B such that each edge connects a vertex from A to B.

Correct choice is (c) C

The best explanation: We can prove it in this following way. Let ‘1’ be a vertex in bipartite set X and let ‘2’ be a vertex in the bipartite set Y. Therefore the bipartite set X contains all odd numbers and the bipartite set Y contains all even numbers. Now let us CONSIDER a graph of odd cycle (a triangle). There exists an edge from ‘1’ to ‘2’, ‘2’ to ‘3’ and ‘3’ to ‘1’. The latter case (‘3’ to ‘1’) makes an edge to EXIST in a bipartite set X itself. Therefore telling us that graphs with odd cycles are not bipartite.

Right CHOICE is (a) NUMBER of vertices in U=Number of vertices in V

Easiest EXPLANATION - We KNOW that in a bipartite graph sum of DEGREES of vertices in U=sum of degrees of vertices in V. Given that the graph is a k-regular bipartite graph, we have k*(number of vertices in U)=k*(number of vertices in V).

The correct answer is (b) Sum of degrees of vertices in U = Sum of degrees of vertices in V

Easiest explanation - We can prove this by INDUCTION. By adding one edge, the degree of vertices in U is EQUAL to 1 as well as in V. Let us assume that this is true for n-1 edges and ADD one more edge. Since the given edge ADDS exactly once to both U and V we can tell that this statement is true for all n vertices.