0

Can anyone explain this question. In an undirected graph $G$, the number of vertices having odd and even degrees are $M$ and $N$ respectively. Which of these values are possible for $M$ and $N$?

  1. $M = 96, N = 11$

  2. $M = 101, N = 10$

  3. $M = 97, N = 31$

  4. $M = 103, N = 12$

terran
  • 1,380
Lilly
  • 1

1 Answers1

1

$M$, the number of odd degree vertices has to be even, see

Proving that the number of vertices of odd degree in any graph G is even.

This leaves only answer A, which must then be correct be the exclusion principle.

Matteo
  • 745