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

View Answer

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

View Answer

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(n^{3})

b) linear time

c) O(1)

d) O(nlogn)

View Answer

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(n

^{2}) edges.

4. The partition V = V_{1} ∪ V_{2} in a bipartite graph G_{1} is called ________

a) bipartition of G_{1}

b) 2-vertex set of G_{1}

c) sub bipartite graphs

d) disjoint vertex set

View Answer

Explanation: A graph G

_{1}(V, E) is called bipartite if its vertex set V(G) can be decomposed into two non-empty disjoint subsets V

_{1}(G

_{1}) and V2(G

_{1}) in such a way that each edge e ∈ E(G) has its one end joint in V

_{1}(G

_{1}) and other endpoint in V

_{2}(G

_{1}). The partition V = V

_{1}∪ V

_{2}in a bipartite graph G

_{1}is called bipartition of G

_{1}.

5. What is the maximum number of edges in a bipartite graph on 14 vertices?

a) 78

b) 15

c) 214

d) 49

View Answer

Explanation: By definition, the maximum possible number of edges in a bipartite graph on ‘n’ vertices = (1/4) x n

^{2}.

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) 2^{10}

d) 412

View Answer

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

View Answer

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

View Answer

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

View Answer

Explanation: The below bipartite graph is not a complete graph as there is no edge between A-B, B-C, C-D, C-Q, P-Q, Q-R, Q-D and so it is not a complete graph.

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

View Answer

Explanation: A graph is bipartite if and only if it does not contain an odd cycle. The spectrum of a graph is symmetric if and only if it is a bipartite graph. These are the characteristics of the graph.

**Sanfoundry Global Education & Learning Series – Discrete Mathematics.**

To practice all areas of Discrete Mathematics, __here is complete set of 1000+ Multiple Choice Questions and Answers__.