# Bipartite Graph Multiple choice Questions and Answers (MCQs)

## Click on any option to know the CORRECT ANSWERS

 Question 1
Given G is a bipartite graph and the bipartitions of this graphs are U and V respectively. What is the relation between them?
 A Number of vertices in U = Number of vertices in V B Sum of degrees of vertices in U = Sum of degrees of vertices in V C Number of vertices in U > Number of vertices in V D Nothing can be said

Question 1 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.

 Question 2
A k-regular bipartite graph is the one in which degree of each vertices is k for all the vertices in the graph. Given that the bipartitions of this graph are U and V respectively. What is the relation between them?
 A Number of vertices in U=Number of vertices in V B Number of vertices in U not equal to number of vertices in V C Number of vertices in U always greater than the number of vertices in V D Nothing can be said

Question 2 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).

 Question 3
There are four students in a class namely A, B, C and D. A tells that a triangle is a bipartite graph. B tells pentagon is a bipartite graph. C tells square is a bipartite graph. D tells heptagon is a bipartite graph. Who among the following is correct?
 A A B B C C D D

Question 3 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.

 Question 4
A complete bipartite graph is a one in which each vertex in set X has an edge with set Y. Let n be the total number of vertices. For maximum number of edges, the total number of vertices hat should be present on set X is?
 A n B n/2 C n/4 D data insufficient

Question 4 Explanation:
We can prove this by calculus. Let x be the total number of vertices on set X. Therefore set Y will have n-x. We have to maximize x*(n-x). This is true when x=n/2.

 Question 5
When is a graph said to be bipartite?
 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 B If the graph is connected and it has odd number of vertices C If the graph is disconnected D If the graph has at least n/2 vertices whose degree is greater than n/2