# Bipartite Graphs MCQ

1. The maximum number of edges in a bipartite graph on 14 vertices is ___________

a) 56

b) 14

c) 49

d) 87

Answer: c

A maximum number of edges occurs in a complete bipartite graph when every vertex has an edge to every opposite vertex in the graph.

A number of edges in a complete bipartite graph are 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

Answer: c

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)

Answer: b

- 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 the 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 = 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

Answer: b

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 it’s one end joint in V1(G1) and another endpoint in V2(G1).

The partition V = V1 ∪ V2 in a bipartite graph G1 is called the 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

Answer: d

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

Substituting n = 14, we get the maximum number of edges in a bipartite graph on 14 vertices,= (1/4) x (14)2

= (1/4) x 14 x 14

= 49

∴ A 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

Answer: b

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

7. Bipartite graphs are used in ________

a) modern coding theory

b) coloring graphs

c) neural networks

d) chemical bonds

Answer: a

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

Answer: b

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

Answer: a

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.

1. Which type of graph has no odd cycle in it?

a) Bipartite

b) Histogram

c) Cartesian

d) Pie

Answer: a

The graph is known as Bipartite if the graph does not contain any odd length cycle in it. Odd length cycle means a cycle with an odd number of vertices in it.

2. What type of graph has a chromatic number less than or equal to 2?

a) Histogram

b) Bipartite

c) Cartesian

d) Tree

Answer: b

A graph is known as a bipartite graph if and only if it has the total chromatic number less than or equal to 2. The smallest number of graphs needed to color the graph is its chromatic number.

3. Which of the following is the correct type of spectrum of the bipartite graph?

a) Symmetric

b) Anti – Symmetric

c) Circular

d) Exponential

Answer: a

The spectrum of the bipartite graph is symmetric in nature. The spectrum is the property of graphs that are related to polynomial, Eigen values, and Eigen vectors of the matrix related to the graph.

4. Which of the following is not a property of the bipartite graph?

a) No Odd Cycle

b) Symmetric spectrum

c) Chromatic Number Is Less Than or Equal to 2

d) Asymmetric spectrum

Answer: d

A graph is known to be bipartite if it has an odd length cycle number. It also has a symmetric spectrum and the bipartite graph contains the total chromatic number less than or equal to 2.

5. Which one of the following is the chromatic number of the bipartite graph?

a) 1

b) 4

c) 3

d) 5

Answer: a

A graph is known as a bipartite graph if and only if it has the total chromatic number less than or equal to 2. The smallest number of graphs needed to color the graph is the chromatic number.

6. Which graph has a size of minimum vertex cover equal to maximum matching?

a) Cartesian

b) Tree

c) Heap

d) Bipartite

Answer: d

The Konig’s theorem gives the equivalence relation between the minimum vertex cover and the maximum matching in graph theory. The bipartite graph has a size of minimum vertex cover equal to maximum matching.

7. Which theorem gives the relation between the minimum vertex cover and maximum matching?

a) Konig’s Theorem

b) Kirchhoff’s Theorem

c) Kuratowski’s Theorem

d) Kelman Theorem

Answer: a

The Konig’s theorem given the equivalence relation between the minimum vertex cover and the maximum matching in graph theory. The bipartite graph has a size of minimum vertex cover equal to maximum matching.

8. Which of the following is not a property of a perfect graph?

a) Compliment of Line Graph of Bipartite Graph

b) Compliment of Bipartite Graph

c) Line Graph of Bipartite Graph

d) Line Graph

Answer: d

The Compliment of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph, and every Bipartite Graph is known as a perfect graph in graph theory.

A normal line graph is not a perfect graph whereas a line perfect graph is a graph whose line graph is a perfect graph.

9. Which of the following graphs doesn’t have a chromatin number less than or equal to 2?

a) Compliment of Line Graph of Bipartite Graph

b) Compliment of Bipartite Graph

c) Line Graph of Bipartite Graph

d) Wheel graph

Answer: d

The perfect bipartite graph has chromatic number 2. Also, the Compliment of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph, and every Bipartite Graph is known as a perfect graph in graph theory.

Wheel graph Wn has chromatin number 3 if n is odd and 4 if n is even.

10. Which of the following has a maximum clique size of 2?

a) Perfect graph

b) Tree

c) Histogram

d) Cartesian

Answer: a

The perfect bipartite graph has clique size 2. Also, the clique size of Compliment of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph, and every Bipartite Graph is 2.

11. What is the chromatic number of compliments of the line graph of the bipartite graph?

a) 0

b) 1

c) 2

d) 3

Answer: c

The perfect bipartite graph has chromatic number 2. So the Compliment of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph, and every Bipartite Graph has chromatic number 2.

12. What is the clique size of the line graph of the bipartite graph?

a) 0

b) 1

c) 2

d) 3

Answer: c

The perfect bipartite graph has clique size 2. So the clique size of Compliment of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph, and every Bipartite Graph is 2.

13. It is possible to have a negative chromatic number on a bipartite graph.

a) True

b) False

Answer: b

A graph is known as a bipartite graph if and only if it has the total chromatic number less than or equal to 2.

The smallest number of graphs needed to color the graph is the chromatic number. But the chromatic number cannot be negative.

14. Every Perfect graph has forbidden graph characterization.

a) True

b) False

Answer: a

Berge theorem proves the forbidden graph characterization of every perfect graph. Because of that reason every bipartite graph is a perfect graph.

15. Which structure can be modeled by using a bipartite graph?

a) Hypergraph

b) Perfect Graph

c) Hetero Graph

d) Directed Graph

Answer: a

A combinatorial structure such as Hypergraph can be made using the bipartite graphs. A hypergraph in graph theory is a type of graph in which an edge can join any number of vertices.

1. Which type of graph has all the vertex of the first set connected to all the vertex of the second set?

a) Bipartite

b) Complete Bipartite

c) Cartesian

d) Pie

Answer: b

The graph is known as Bipartite if the graph does not contain any odd length cycle in it. The complete bipartite graph has all the vertex of the first set connected to all the vertex of the second set.

2. Which graph is also known as biclique?

a) Histogram

b) Complete Bipartite

c) Cartesian

d) Tree

Answer: b

A graph is known as a complete bipartite graph if and only if it has all the vertex of the first set connected to all the vertex of the second set. Complete Bipartite graph is also known as Biclique.

3. Which term defines all the complete bipartite graphs that are trees?

a) Symmetric

b) Anti – Symmetric

c) Circular

d) Stars

Answer: d

Star is a complete bipartite graph with one internal node and k leaves. Therefore, all complete bipartite graph which is trees is known as stars in graph theory.

4. How many edges does an n vertex triangle-free graph contains?

a) n^{2}

b) n^{2} + 2

c) n^{2} / 4

d) n^{3}

Answer: c

A n vertex triangle-free graph contains a total of n^{2} / 4 number of edges. This is stated by Mantel’s Theorem which is a special case in Turan’s theorem for r=2.

5. Which graph is used to define the claw-free graph?

a) Bipartite Graph

b) Claw Graph

c) Star Graph

d) Cartesian Graph

Answer: b

Star is a complete bipartite graph with one internal node and k leaves. Star with three edges is called a claw. Hence this graph is used to define a claw-free graph.

6. What is the testing of a complete bipartite subgraph in a bipartite graph problem called?

a) P Problem

b) P-Complete Problem

c) NP Problem

d) NP-Complete Problem

Answer: d

NP stands for nondeterministic polynomial time. In a bipartite graph, the testing of a complete bipartite subgraph in a bipartite graph is an NP-Complete Problem.

7. Which graph cannot contain K3, 3 as a minor of the graph?

a) Planar Graph

b) Outer Planar Graph

c) Non-Planar Graph

d) Inner Planar Graph

Answer: a

The minor graph is formed by deleting a certain number of edges from a graph or by deleting a certain number of vertices from a graph. Hence Planar graph cannot contain K3, 3 as a minor graph.

8. Which of the following is not an Eigen value of the adjacency matrix of the complete bipartite graph?

a) (nm)^{1/2}

b) (-nm)^{1/2}

c) 0

d) nm

Answer: d

The adjacency matrix is a square matrix that is used to represent a finite graph. Therefore, the Eigen values for the complete bipartite graph are found to be (nm)^{1/2}, (-nm)^{1/2}, 0.

9. Which complete graph is not present in the minor of the Outer Planar Graph?

a) K3, 3

b) K3, 1

c) K3, 2

d) K1, 1

Answer: c

The minor graph is formed by deleting a certain number of edges from a graph or by deleting a certain number of vertices from a graph. Hence Outer Planar graph cannot contain K3, 2 as a minor graph.

10. Is every complete bipartite graph a Moore Graph?

a) True

b) False

Answer: a

In graph theory, Moore’s graph is defined as a regular graph that has a degree d and diameter k. therefore, every complete bipartite graph is a Moore Graph.

11. What is the multiplicity for the adjacency matrix of complete bipartite graph for 0 Eigen value?

a) 1

b) n + m – 2

c) 0

d) 2

Answer: b

The adjacency matrix is a square matrix that is used to represent a finite graph. The multiplicity of the adjacency matrix of a complete bipartite graph with Eigen Value 0 is n + m – 2.

12. Which of the following is not an Eigen value of the Laplacian matrix of the complete bipartite graph?

a) n + m

b) n

c) 0

d) n*m

Answer: d

The Laplacian matrix is used to represent a finite graph in the mathematical field of Graph Theory. Therefore, the Eigen values for the complete bipartite graph are found to be n + m, n, m, 0.

13. What is the multiplicity for the Laplacian matrix of the complete bipartite graph for n Eigen value?

a) 1

b) m-1

c) n-1

d) 0

Answer: b

The Laplacian matrix is used to represent a finite graph in the mathematical field of Graph Theory. The multiplicity of the Laplacian matrix of a complete bipartite graph with Eigen Value n is m-1.

14. Is it true that every complete bipartite graph is a modular graph?

a) True

b) False

Answer: a

Yes, the modular graph in graph theory is defined as an undirected graph in which all three vertices have at least one median vertex. So all complete bipartite graph is called a modular graph.

15. How many spanning trees does a complete bipartite graph contain?

a) nm

b) m^{n-1} * n^{n-1}

c) 1

d) 0

Answer: b

The spanning tree of a given graph is defined as the subgraph or the tree with all the given vertices but having a minimum number of edges. So, there are a total of mn-1 * nn-1 spanning trees for a complete bipartite graph.