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?

1. Planar
2. Non-Planar
3. Isomorphic
4. 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 __?

1. Vertices
2. Edges
3. Endpoints
4. 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?

1. One or more
2. Two or more
3. Three or more
4. 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?

1. An Infinite
2. No Infinite
3. No Plane
4. 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 ____?

1. Finite
2. Infinite
3. Zero
4. 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?

1. One
2. Two
3. Five
4. 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?

1. Bipartite planar graph
2. Complete planar graph
3. Connected planar graph
4. 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. 1
2. 2
3. 3
4. 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?

1. 3v-e≥6
2. 3v-e≤6
3. 3v+e≥6
4. 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?

1. n≥5
2. n>5
3. n<5
4. 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 K_mn?

1. m<3
2. n>3
3. Both A and B
4. 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 K_mn

---

12. When no edge crosses over another, a graph is ____?

1. Planar
2. Non-planar
3. Non-circular
4. 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 K₅ or K_3,3?

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

Answer: B) Homeomorphic

Explanation:

In order for a graph to be non-planar, it must contain a subgraph that is homeomorphic to K₅ or K_3,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?

1. Adjacent
2. Complement
3. Supplement
4. 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 ____?

1. M
2. N
3. O
4. 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?

1. Similar
2. Differently
3. Same
4. 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?

1. Minimum
2. Maximum
3. Average
4. 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 -?

1. G(x)
2. x(G)
3. G
4. 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?

1. Bipartite Graph Checking
2. Register Allocation
3. Map Coloring
4. All of the above

Answer: D) All of the above

Explanation:

The following are the applications of graph coloring -

1. Bipartite Graph Checking
2. Register Allocation
3. 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?

1. One
2. Two
3. Three
4. 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 -?

1. ∑_v∈Vdeg(2e)=v
2. ∑_v∈Vdeg(e)=2v
3. ∑_v∈Vdeg(2v)=e
4. ∑_v∈Vdeg(v)=2e

Answer: D) ∑_v∈Vdeg(v)=2e

Explanation:

Mathematically handshaking theorem can be stated as ∑_v∈Vdeg(v)=2e.

---

---