Graph Theory Quiz-2 (Theorem 1 and 2)

Which of the following always holds true for any undirected graph?

• The number of edges equals the number of vertices

• The sum of degrees equals the number of vertices

• The number of odd degree vertices is even

• Every graph has at least one vertex of degree 2

Which statement about degrees is incorrect?

• The degree sum of a graph is even

• A vertex can have degree greater than the number of vertices

• An isolated vertex contributes zero to the degree sum

• A loop contributes 2 to the degree of a vertex

The total number of odd-degree vertices in a graph is always:

• Prime

• Even

• Odd

• Zero or even, depending on the graph

A graph with 6 vertices has 5 vertices of odd degree. Which statement is true?

• The graph is complete

• One vertex must be isolated

• This graph cannot exist

• Total degree = number of vertices × number of edges

Which is a valid interpretation of Theorem 1?

• The number of edges equals half the number of vertices

• Each edge adds 2 to the degree sum

• The number of odd-degree vertices equals the number of even-degree vertices

• Every vertex must have even degree

Theorem 2 is a corollary of Theorem 1 because:

• All graphs are even graphs

• The total degree is even only if odd degree vertices are even in number

• No vertex can have degree zero

• It is directly stated in Euclidean geometry

A graph has 8 vertices and 12 edges. What is the total degree?

• 12

• 24

• 16

• 20

A graph has 6 vertices of degree 3. How many edges are there?

• 9

• 12

• 18

• Not possible

If the sum of degrees in a graph is 44, how many edges does it have?

• 22

• 44

• 11

• Cannot determine

A graph has 10 edges and 2 vertices of degree 1. The rest are degree 2. How many vertices?

• 10

• 12

• 9

• 11