# Discrete Mathematics | Week 8

## Quiz

Link : Discrete Mathematics Week 8 (nptel.ac.in)

1. What is the number of colors required to color a complete graph containing n vertices?

d. n

Explanation

2. Which of the following graphs does not have a Eulerian circuit?

Explanation

3. What is the number of edges for a connected planar graph having 8 vertices, and 6 regions?

a. 12

Explanation

4. Which of the following graphs can be concluded to be Hamiltonian?

a. A graph with the number of edges of every node, greater than 𝑛/2

d. k6

Explanation

5. Find the total number of edges in the complement graph 𝐺𝑐 , where 𝐺 has 12 vertices and 34 edges.

b. 32

Explanation

6. Which of the following statement(s) is/are true?

I) We can find a tree that is not planar.

II) We can conclude that a graph is connected if the degree of all the vertices is

greater than equal to 𝑛/2.

III) Given a graph G, there is a cycle of length 𝑘 and 𝑘 is less than equal to n𝑛, then we can find a path of length at least 𝑘+1.

d. II and III

Explanation

7. A graph where we can traverse through all the vertices, without repeating edges or vertices more than once is called?

c. Hamiltonian graph

Explanation

8. State whether true/false:
A bipartite graph can have an odd cycle.

b. False

Explanation

9. What is the cardinality of the set of edges of the complement of a complete graph 𝐺 having 5 vertices?

c. 0

Explanation

10. What is the chromatic number of the graph given below respectively?

d.  3,3

Explanation 2
0 