# Discrete Mathematics Questions and Answers – Bipartite Graphs

«
»

This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Bipartite Graphs”.

1. The maximum number of edges in a bipartite graph on 14 vertices is ___________
a) 56
b) 14
c) 49
d) 87

Explanation: Maximum number of edges occur in a complete bipartite graph when every vertex has an edge to every opposite vertex in the graph. Number of edges in a complete bipartite graph is a*b, where a and b are no. of vertices on each side. This quantity is maximum when a = b i.e. when there are 7 vertices on each side. So answer is 7 * 7 = 49.

2. In a ______ the degree of each and every vertex is equal.
a) regular graph
b) point graph
c) star graph
d) euler graph

Explanation: A regular graph has the same degree in each of its vertices. In a regular bipartite graph, if the common degree of each vertices is 1, the two parts are of the same size.

3. The time complexity to test whether a graph is bipartite or not is said to be _______ using depth first search.
a) O(n3)
b) linear time
c) O(1)
d) O(nlogn)

Explanation: It is possible to test whether a graph is bipartite, and to return either a two-coloring (if it is bipartite) or an odd cycle (if it is not) in linear time i.e, O(n) using depth first search. In case of the intersection of n line segments or other simple shapes in the Euclidean graph, it is possible to test whether the graph is bipartite and it will return either a two-coloring or an odd cycle in time O(nlogn), even though the graph itself has up to O(n2) edges.

4. The partition V = V1 ∪ V2 in a bipartite graph G1 is called ________
a) bipartition of G1
b) 2-vertex set of G1
c) sub bipartite graphs
d) disjoint vertex set

Explanation: A graph G1(V, E) is called bipartite if its vertex set V(G) can be decomposed into two non-empty disjoint subsets V1(G1) and V2(G1) in such a way that each edge e ∈ E(G) has its one end joint in V1(G1) and other endpoint in V2(G1). The partition V = V1 ∪ V2 in a bipartite graph G1 is called bipartition of G1.

5. What is the maximum number of edges in a bipartite graph on 14 vertices?
a) 78
b) 15
c) 214
d) 49

Explanation: By definition, the maximum possible number of edges in a bipartite graph on ‘n’ vertices = (1/4) x n2.
Substituting n = 14, we get maximum number of edges in a bipartite graph on 14 vertices,= (1/4) x (14)2
= (1/4) x 14 x 14
= 49
∴ Maximum number of edges in a bipartite graph on 14 vertices = 49.

6. In a complete bipartite graph, the intersection of two sub graphs is ______
a) 1
b) null
c) 210
d) 412

Explanation: In a complete Bipartite graph, there must exist a partition say, V(G)=X∪Y and X∩Y=∅, that means all edges share a vertex from both set X and Y.

7. Bipartite graphs are used in ________
a) modern coding theory
b) colouring graphs
c) neural networks
d) chemical bonds

Explanation: All types of cyclic graphs are examples of cyclic graphs. A cyclic graph is considered bipartite if all the cycles involved are of even length. Bipartite graphs are widely used in modern coding theory apart from being used in modeling relationships.

8. All closed walks are of ______ length in a bipartite graph.
a) infinite
b) even
c) odd
d) odd prime

Explanation: In a bipartite graph G all closed walks must be of even length as well as all cycles in G are of even length. Then only the graph is considered a bipartite graph.

9. Every complete bipartite graph must not be _______
a) planar graph
b) line graph
c) complete graph
d) subgraph

10. The spectrum of a graph is _______ if and only if it is _______ graph.
a) symmetry, bipartite
b) transitive, bipartite
c) cyclic, Euler
d) reflexive, planar 