×

# 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

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

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

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

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

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

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

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

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

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

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?

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 Kmn

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

1. Planar
2. Non-planar
3. Non-circular
4. None

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?

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

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?

2. Complement
3. Supplement
4. Vertical

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

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

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

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

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

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

Explanation:

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