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
- n2
Answer: C) n-1
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)?
- 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 V1, while n is the number of vertices in V2?
- Kmn
- Kn
- Km
- NMk
Answer: A) Kmn
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?
- 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.