Data Structures & Algorithms Multiple Choice Questions 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
Answer: b
Clarification: 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
Answer: a
Clarification: 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
Answer: c
Clarification: 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
Answer: b
Clarification: 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
Answer: a
Clarification: 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
Answer: a
Clarification: 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
Answer: a
Clarification: 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
Answer: a
Clarification: 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
Answer: a
Clarification: 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
Answer: b
Clarification: 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.