This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Planarity, Degree and Coloring of Graph”.
1. The chromatic number of a graph is the property of ____________
a) graph coloring
b) graph ordering
c) group ordering
d) group coloring
View Answer
Explanation: A graph coloring is an assignment of labels to the vertices of a graph such that no two adjacent vertices share the same labels is called the colors of the graph. Now, the chromatic number of any graph is the minimal number of colors for which such an assignment is possible.
2. If a graph G is k-colorable and k<n, for any integer n then it is ___________
a) n-colorable
b) n2 nodes
c) (k+n)-colorable
d) (k3+n3+1) nodes
View Answer
Explanation: The chromatic number of a graph is the minimal number of colors for which a graph coloring is possible. A graph G is termed as k-colorable if there exists a graph coloring on G with k colors. If a graph is k-colorable, then it is n-colorable for any n>k.
3. If Cn is the nth cyclic graph, where n>3 and n is odd. Determine the value of X(Cn).
a) 32572
b) 16631
c) 3
d) 310
View Answer
Explanation: Here n is odd and X(Cn)! = 2. Since there are two adjacent edges in Cn. Now, a graph coloring for Cn exists where vertices are colored red and blue alternatively and another edge is with a different colour say orange, then the value of X(Cn) becomes 3.
4. Determine the density of a planar graph with 34 edges and 13 nodes.
a) 22/21
b) 12/23
c) 328
d) 576
View Answer
Explanation: The density of a planar graph or network is described as the ratio of the number of edges(E) to the number of possible edges in a network with(N) nodes. So, D = E − N + 1/ 2 N − 5. Hence, the required answer is: D=(34-13+1)/(2*13-5) = 22/21. A completely sparse planar graph has density 0 and a completely dense planar graph has degree 1.
5. If the number of vertices of a chromatic polynomial PG is 56, what is the degree of PG?
a) 344
b) 73
c) 265
d) 56
View Answer
Explanation: The chromatic polynomial PG of a graph G is a polynomial in which every natural number k returns the number PG(k) of k-colorings of G. Since, the degree of PG is equal to the number of vertices of G, the required answer is 56.
6. For a connected planar simple graph G=(V, E) with e=|E|=16 and v=|V|=9, then find the number of regions that are created when drawing a planar representation of the graph?
a) 321
b) 9
c) 1024
d) 596
View Answer
Explanation: We know that the number of regions in a planar representation of the graph is r=e-v+2, then the required answer is r=16-9+2=9.
7. For a connected planar simple graph G=(V, E) with e=|E|=16 and v=|V|=9, then find the number of regions that are created when drawing a planar representation of the graph?
a) 321
b) 9
c) 1024
d) 596
View Answer
Explanation: Note that K3,3 and K5 are the “smallest” non-planar graphs because in that every non-planar graph contains them. According to Kuratowski’s theorem, a graph is defined as non-planar if and only if it contains a subgraph homomorphic to K3,3 or K5.
8. Suppose G be a connected planar graph of order n≥5 and size m. If the length of the smallest cycle in G is 5, then which of the following is true?
a) (m+n)4>=mn
b) m≤5/3(n−2)
c) (m2+n)/3
d) n>=(6/5)(n+1)
View Answer
Explanation: Because G is connected and planar, Euler’s theorem is bound to be involved. Let f denote the number of faces so that n−m+f=2. Because the length of the smallest cycle in G is 5, every face has at least 5 edges adjacent to it. This means 2m≥5f because every edge is adjacent to two faces. Plugging this in yields 2=n−m+f≤n−m+2/5m=n−3/5m, and hence m≤5/3(n−2).
9. What is the number of edges of the greatest planar subgraph of K3,2 where m,n≤3?
a) 18
b) 6
c) 128
d) 702
View Answer
Explanation: The plane graph with an edge at most 6+2(m−3) is the greatest planar graph. So, in this case the number of edges is 6.
10. A non-planar graph can have ____________
a) complete graph
b) subgraph
c) line graph
d) bar graph
View Answer
Explanation: A non-planar graph can have removed edges and vertices so that it contains subgraphs. However, non-planar graphs cannot be drawn in a plane and so no edge of the graph can cross it.
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Apply for Computer Science Internship
- Apply for BCA Internship
- Practice BCA MCQs
- Check Computer Science Books
- Practice Information Technology MCQs
