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
View Answer

Answer: c
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.
advertisement

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

Answer: c
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)
View Answer

Answer: b
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
View Answer

Answer: b
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
View Answer

Answer: d
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.
advertisement

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

Answer: b
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

Answer: a
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

Answer: b
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

Answer: c
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.
discrete-mathematics-questions-answers-bipartite-graphs-q9
advertisement

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

Answer: a
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.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn