Home » MCQs » Discrete Mathematics MCQs

Discrete Mathematics | Isomorphic, Homeomorphic, Regular and Bipartite Graphs MCQs

Discrete Mathematics | Isomorphic, Homeomorphic, Regular and Bipartite Graphs MCQs: This section contains multiple-choice questions and answers on Isomorphic, Homeomorphic, Regular and Bipartite Graphs in Discrete Mathematics.
Submitted by Anushree Goswami, on July 27, 2022

1. When two graphs such as G(V, E) and G* (V*, E*) have a one-to-one correspondence, they are said to be ____?

1. Isomorphic
2. Homeomorphic
3. Both A and B
4. None of the above

Answer: A) Isomorphic

Explanation:

When two graphs such as G(V, E) and G* (V*, E*) have a one-to-one correspondence, they are said to be isomorphic.

---

2. Homeomorphic graphs are those in which G and G* are derived from the ___ graphs?

1. Same
2. Isomorphic
3. Both A and B
4. None of the above

Answer: C) Both A and B

Explanation:

Homeomorphic graphs are those in which G and G* are derived from the same graph or are isomorphic graphs.

---

3. G'=(V', E') is a subgraph of graph G=(V, E), where each edge in G' has the same end vertex as ____?

1. G
2. V'⊆V
3. E'⊆E
4. All of the above

Answer: D) All of the above

Explanation:

G'=(V', E') is a subgraph of graph G=(V, E), where each edge in G' has the same end vertex as G and V'⊆V and E'⊆E.

---

4. A/an ____ vertex makes up a subgraph?

1. Individual
2. Double
3. Triple
4. Multiple

Answer: A) Individual

Explanation:

An individual vertex makes up a subgraph.

---

5. If G1 contains all the vertices of G, it is called a ____ subgraph of G?

1. Isomorphic
2. Homeomorphic
3. Spanning
4. None of the above

Answer: C) Spanning

Explanation:

If G1 contains all the vertices of G, it is called a spanning subgraph of G.

---

6. Every vertex in G must be connected to every other vertex in G for a graph G to be considered ____?

1. Complete
2. Regular
3. Bipartite
4. Isomorphic

Answer: A) Complete

Explanation:

Every vertex in G must be connected to every other vertex in G for a graph G to be considered complete.

---

7. If all its vertices have the same degree K, the graph is called _____?

1. Regular
2. K-regular
3. Both A and B
4. None of the above

Answer: C) Both A and B

Explanation:

If all its vertices have the same degree K, the graph is called regular or K-regular.

---

8. _-regular graphs are graphs whose vertices all have degree 2?

1. 0
2. 1
3. 2
4. K

Answer: C) 2

Explanation:

2-regular graphs are graphs whose vertices all have degree 2.

---

9. ^{Graphs of degree ___ are complete graphs K_n}?

1. n
2. n+1
3. n-1
4. n²

Answer: C) n-1

Explanation:

Graphs of degree n-1 are complete graphs K_n.

---

10. An edge of G that connects two vertices of V1 to vertices of V2 is said to be connected by a ____ graph G=(V, E)?

1. Isomorphic
2. Homeomorphic
3. Bipartite
4. Regular

Answer: C) Bipartite

Explanation:

An edge of G that connects two vertices of V1 to vertices of V2 is said to be connected by a bipartite graph G=(V, E).

---

11. A bipartite graph is denoted by ___, where m is the number of vertices in V₁, while n is the number of vertices in V₂?

1. K_mn
2. K_n
3. K_m
4. NM_k

Answer: A) K_mn

Explanation:

A bipartite graph is denoted by K_mn, where m is the number of vertices in V₁, while n is the number of vertices in V₂.

---

12. If each vertex of V1 is connected to each vertex of V2, a graph G = (V, E) is considered a ____ graph?

1. Complete Bipartite
2. Incomplete Bipartite
3. Connected Bipartite
4. Disconnected Bipartite

Answer: A) Complete Bipartite

Explanation:

If each vertex of V1 is connected to each vertex of V2, a graph G = (V, E) is considered a complete bipartite graph.

---

13. As each of the m vertices is connected to each of the n vertices, a complete bipartite graph consists of ___ edges?

1. m+n
2. m-n
3. m.n
4. m/n

Answer: C) m.n

Explanation:

As each of the m vertices is connected to each of the n vertices, a complete bipartite graph consists of m.n edges.

---

14. ____ Paths contain every edge of a graph exactly once in their edge lists.?

1. Euler
2. Bipartite
3. Regular
4. Isomorphic

Answer: A) Euler

Explanation:

Euler Paths contain every edge of a graph exactly once in their edge lists.

---

15. Euler circuits go through graphs by repeatedly presenting the same initial vertex as the ____ vertex?

1. Initial
2. Terminal
3. Middle
4. Central

Answer: B) Terminal

Explanation:

Euler circuits go through graphs by repeatedly presenting the same initial vertex as the terminal vertex.

---

16. Euler Graphs are graphs that contain Euler ____.

1. Points
2. Dots
3. Circuits
4. None

Answer: C) Circuits

Explanation:

Euler Graphs are graphs that contain Euler Circuits.

---

17. Vertices may be repeated in an Euler Circuit, but edges are used exactly ____?

1. Once
2. Twice
3. Thrice
4. None

Answer: A) Once

Explanation:

Vertices may be repeated in an Euler Circuit, but edges are used exactly once.

---

18. For a graph with no ___-degree vertices, we can produce an Euler Circuit?

1. Odd
2. Even
3. Same
4. Different

Answer: A) Odd

Explanation:

For a graph with no odd-degree vertices, we can produce an Euler Circuit.

---

---