This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Bipartite Graph”.

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

View Answer

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.

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

View Answer

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

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

View Answer

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.

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

View Answer

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.

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

View Answer

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.

6. Are trees bipartite?

a) Yes

b) No

c) Yes if it has even number of vertices

d) No if it has odd number of vertices

View Answer

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.

7. A graph has 20 vertices. The maximum number of edges it can have is? (Given it is bipartite)

a) 100

b) 140

c) 80

d) 20

View Answer

Explanation: 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.

8. Given that a graph contains no odd cycle. Is it enough to tell that it is bipartite?

a) Yes

b) No

View Answer

Explanation: It is required that the graph is connected also. If it is not then it cannot be called a bipartite graph.

9. Can there exist a graph which is both eulerian and is bipartite?

a) Yes

b) No

c) Yes if it has even number of edges

d) Nothing can be said

View Answer

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.

10. A graph is found to be 2 colorable. What can be said about that graph?

a) The given graph is eulerian

b) The given graph is bipartite

c) The given graph is hamiltonian

d) The given graph is planar

View Answer

Explanation: 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.

**Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.**

To practice all areas of Data Structures & Algorithms, __here is complete set of 1000+ Multiple Choice Questions and Answers__.