Question 25

Let $G = (V, E)$ be any undirected graph with vertex set $V$ and edge set $E$.

1. By Euler's Handshaking Lemma:

   $$\sum_{v \in V} \text{deg}(v) = 2 |E|$$

   Because $2 |E|$ is an integer multiple of 2, the sum of the degrees of all vertices is always an even number.
   Therefore, statement Q is TRUE.

2. Partition the vertex set $V$ into $V_{\text{even}}$ (vertices with even degree) and $V_{\text{odd}}$ (vertices with odd degree):

   $$\sum_{v \in V} \text{deg}(v) = \sum_{v \in V_{\text{even}}} \text{deg}(v) + \sum_{v \in V_{\text{odd}}} \text{deg}(v) = 2 |E|$$

   The sum $\sum_{v \in V_{\text{even}}} \text{deg}(v)$ is a sum of even integers, which is even.
   Subtracting this even sum from the total even sum $2|E|$ leaves $\sum_{v \in V_{\text{odd}}} \text{deg}(v)$ as an even integer.
   A sum of odd numbers can be even if and only if there is an even number of odd numbers.
   Therefore, $|V_{\text{odd}}|$ must be even, meaning the number of odd-degree vertices is always even.
   Therefore, statement P is TRUE.

Both P and Q are TRUE (Option C).