Discrete Mathematics Questions and Answers – Planarity, Degree and Coloring of Graph

«
»

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

Answer: b
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.
advertisement

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

Answer: a
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

Answer: c
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

Answer: a
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

Answer: d
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.
advertisement

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

Answer: b
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

Answer: b
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

Answer: b
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

Answer: b
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.
advertisement

10. A non-planar graph can have ____________
a) complete graph
b) subgraph
c) line graph
d) bar graph
View Answer

Answer: b
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.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn