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

• • • • 3

      • 4

      • n⋅(n−1)/2n

      • n

Correct Answer :n

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

• complete graph with 79 vertices

Correct Answer :

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

• 12

• 14

• 8

• 10

Correct Answer : 14

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

• A graph with the number of edges of every node, greater than n/2

• k6

Correct Answer :A graph with the number of edges of every node, greater than n/2

• k6

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

• 66

• 32

• 33

• 34

Correct Answer : 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 𝐺, there is a cycle of length 𝑘 and 𝑘 is less than equal to 𝑛, then we can find a path of length at least 𝑘+1.

• Only I

• Only III

• I and II

• II and III

• I II and III

Correct Answer : 32

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

• Planar graph

• Complete graph

• Hamiltonian graph

• Eulerian graph

Correct Answer : Hamiltonian graph

8. State whether true/false:

A bipartite graph can have an odd cycle.

• • • True

    • False

Correct Answer : False

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

• 10

• 5

• 0

• 2

Correct Answer : 0

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

• 4,3

• 4,4

• 2,3

• 3,3

Correct Answer : 4,4

WEEK-8 DETAILED SOLUTION