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. k6
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
Explanation
Are these answers correct?