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 ____?**

- Isomorphic
- Homeomorphic
- Both A and B
- 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?**

- Same
- Isomorphic
- Both A and B
- 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 ____?**

- G
- V'⊆V
- E'⊆E
- 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?**

- Individual
- Double
- Triple
- 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?**

- Isomorphic
- Homeomorphic
- Spanning
- 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 ____?**

- Complete
- Regular
- Bipartite
- 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 _____?**

- Regular
- K-regular
- Both A and B
- 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?**

- 0
- 1
- 2
- K

**Answer:** C) 2

**Explanation:**

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

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

- n
- n+1
- n-1
- n
^{2}

**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)?**

- Isomorphic
- Homeomorphic
- Bipartite
- 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 _{1}, while n is the number of vertices in V_{2}?**

- K
_{mn} - K
_{n} - K
_{m} - NM
_{k}

**Answer:** A) K_{mn}

**Explanation:**

A bipartite graph is denoted by K_{mn}, where m is the number of vertices in V_{1}, while n is the number of vertices in V_{2}.

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

- Complete Bipartite
- Incomplete Bipartite
- Connected Bipartite
- 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?**

- m+n
- m-n
- m.n
- 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.?**

- Euler
- Bipartite
- Regular
- 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?**

- Initial
- Terminal
- Middle
- 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 ____.**

- Points
- Dots
- Circuits
- 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 ____?**

- Once
- Twice
- Thrice
- 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?**

- Odd
- Even
- Same
- Different

**Answer:** A) Odd

**Explanation:**

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

Comments and Discussions!