×

Multiple-Choice Questions

Web Technologies MCQs

Computer Science Subjects MCQs

Databases MCQs

Programming MCQs

Testing Software MCQs

Digital Marketing Subjects MCQs

Cloud Computing Softwares MCQs

AI/ML Subjects MCQs

Engineering Subjects MCQs

Office Related Programs MCQs

Management MCQs

More

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 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

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?

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

  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.





Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.