×

# 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

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

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

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

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

Explanation:

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

9. Graphs of degree ___ are complete graphs Kn?

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

Explanation:

Graphs of degree n-1 are complete graphs Kn.

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

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 V1, while n is the number of vertices in V2?

1. Kmn
2. Kn
3. Km
4. NMk

Explanation:

A bipartite graph is denoted by Kmn, where m is the number of vertices in V1, while n is the number of vertices in V2.

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

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

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

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

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

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

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

Explanation:

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