Home »
MCQs »
Discrete Mathematics MCQs
Discrete Mathematics | Planar and Non-Planar Graphs MCQs
Discrete Mathematics | Planar and Non-Planar Graphs MCQs: This section contains multiple-choice questions and answers on Planar and Non-Planar Graphs in Discrete Mathematics.
Submitted by Anushree Goswami, on August 10, 2022
1. A ____ graph is one whose edges do not cross in a plane?
- Planar
- Non-Planar
- Isomorphic
- None of the above
Answer: A) Planar
Explanation:
A planar graph is one whose edges do not cross in a plane.
2. There is a region in a plane that cannot be subdivided further because it is bounded by __?
- Vertices
- Edges
- Endpoints
- None
Answer: B) Edges
Explanation:
There is a region in a plane that cannot be subdivided further because it is bounded by ____.
3. There are ____ regions in a planar graph?
- One or more
- Two or more
- Three or more
- Four or more
Answer: A) One or more
Explanation:
There are one or more regions in a planar graph.
4. There will be _____ region in the planar graph?
- An Infinite
- No Infinite
- No Plane
- Plane
Answer: A) An Infinite
Explanation:
There will be an infinite region in the planar graph.
5. Infinite regions are those in which the area is ____?
- Finite
- Infinite
- Zero
- One
Answer: B) Infinite
Explanation:
Infinite regions are those in which the area is infinite.
6. There is only ___ infinite region in a planar graph?
- One
- Two
- Five
- Ten
Answer: A) One
Explanation:
There is only one infinite region in a planar graph.
7. For a ____ planar graph G, if every edge has 2/3 of its region, then r ≤ ⅔ e?
- Bipartite planar graph
- Complete planar graph
- Connected planar graph
- Disconnected planar graph
Answer: C) Connected planar graph
Explanation:
For a connected planar graph G, if every edge has 2/3 of its region, then r ≤ ⅔ e.
8. Connected planar graph G, whose edges are e, whose vertices are v, and whose regions are r, then v-e+r is equal to _?
- 1
- 2
- 3
- 0
Answer: B) 2
Explanation:
G, whose edges are e, whose vertices are v, and whose regions are r, then v-e+r is equal to 2.
9. A connected planar graph G with e edges and v vertex points has ___ edges?
- 3v-e≥6
- 3v-e≤6
- 3v+e≥6
- 3v+e≤6
Answer: A) 3v-e≥6
Explanation:
A connected planar graph G with e edges and v vertex points has 3v-e≥6 edges.
10. In a complete graph Kn, ___ is the only condition for the graph to be planar?
- n≥5
- n>5
- n<5
- N≤5
Answer: C) n<5
Explanation:
In a complete graph Kn, n<5 is the only condition for the graph to be planar.
11. Planarity is only achieved if ____ for a complete bipartite graph Kmn?
- m<3
- n>3
- Both A and B
- None of the above
Answer: C) Both A and B
Explanation:
Planarity is only achieved if m<3 or n>3 for a complete bipartite graph Kmn
12. When no edge crosses over another, a graph is ____?
- Planar
- Non-planar
- Non-circular
- None
Answer: B) Non-planar
Explanation:
When no edge crosses over another, a graph is non-planar.
13. In order for a graph to be non-planar, it must contain a subgraph that is ___ to K5 or K3,3?
- Isomorphic
- Homeomorphic
- Isolated
- Bipartite
Answer: B) Homeomorphic
Explanation:
In order for a graph to be non-planar, it must contain a subgraph that is homeomorphic to K5 or K3,3
14. In a graph with no multiple edges, a vertex coloring is the assignment of colors to vertices in a way that different colors are assigned to ___ vertices?
- Adjacent
- Complement
- Supplement
- Vertical
Answer: A) Adjacent
Explanation:
In a graph with no multiple edges, a vertex coloring is the assignment of colors to vertices in a way that different colors are assigned to adjacent vertices.
15. An M-Colorable graph G is one that can be colored with ____?
- M
- N
- O
- P
Answer: A) M
Explanation:
An M-Colorable graph G is one that can be colored with M-Colors.
16. A coloring is considered proper when two adjacent vertices u and v are colored ____; otherwise, it is described as improper?
- Similar
- Differently
- Same
- Partially same
Answer: B) Differently
Explanation:
A coloring is considered proper when two adjacent vertices u and v are colored differently; otherwise, it is described as improper.
17. A graph G's chromatic number is the ____ number of colors it needs to be properly colored?
- Minimum
- Maximum
- Average
- Medium
Answer: A) Minimum
Explanation:
A graph G's chromatic number is the minimum number of colors it needs to be properly colored.
18. Chromatic number of G is denoted by -?
- G(x)
- x(G)
- G
- Gx
Answer: B) x(G)
Explanation:
Chromatic number of G is denoted by x(G),
19. Which of the following is/are an/the application(s) of graph coloring?
- Bipartite Graph Checking
- Register Allocation
- Map Coloring
- All of the above
Answer: D) All of the above
Explanation:
The following are the applications of graph coloring -
- Bipartite Graph Checking
- Register Allocation
- Map Coloring
20. Based on the Handshaking Theorem, the sum of the degrees of all the vertices in a graph is equal to ___ times the number of edges?
- One
- Two
- Three
- Four
Answer: B) Two
Explanation:
Based on the Handshaking Theorem, the sum of the degrees of all the vertices in a graph is equal to two times the number of edges.
21. Mathematically handshaking theorem can be stated as -?
- ∑v∈Vdeg(2e)=v
- ∑v∈Vdeg(e)=2v
- ∑v∈Vdeg(2v)=e
- ∑v∈Vdeg(v)=2e
Answer: D) ∑v∈Vdeg(v)=2e
Explanation:
Mathematically handshaking theorem can be stated as ∑v∈Vdeg(v)=2e.