Question

Given an undirected graph G= (V, E) determined by the adjacency matrix as follows:

01001

10111

01010

01101

11010

The number of odd degree vertices of the graph is

Select one

A.2
B.4
C.3
D.1
if anyone knows the question please help me :(

Answer 1

The degree of a vertex is defined as the number of edges that touch the vertex. The (i, j)-th entry of the adjacency matrix tells you whether vertex i touches vertex j (1 if yes, 0 if no). Then the degree of vertex i is equal to the sum of the i-th row in the adjacency matrix.

• vertex 1 : degree = 0 + 1 + 0 + 0 + 1 = 2

• vertex 2 : degree = 1 + 0 + 1 + 1 + 1 = 4

• vertex 3 : degree = 0 + 1 + 0 + 1 + 0 = 2

• vertex 4 : degree = 0 + 1 + 1 + 0 + 1 = 3

• vertex 5 : degree = 1 + 1 + 0 + 1 + 0 = 3

So, the correct answer is A. 2.