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

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

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

**a. ****12**

**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. k _{6}**

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

**b. 32**

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

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

**c. Hamiltonian graph**

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

**b. False**

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

**c. 0**

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

**d. **** 3,3**

Are these answers correct?