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) n^{2} nodes

c) (k+n)-colorable

d) (k^{3}+n^{3}+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(C_{n}).

a) 32572

b) 16631

c) 3

d) 310

View Answer

Explanation: Here n is odd and X(C

_{n})! = 2. Since there are two adjacent edges in C

_{n}. 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(C

_{n}) 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 P_{G} is 56, what is the degree of P_{G}?

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 P

_{G}(k) of k-colorings of G. Since, the degree of P

_{G}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 K

_{3,3}and K

_{5}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 K

_{3,3}or K

_{5}.

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) (m^{2}+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 K_{3,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__.