GATE CS 2013 Q25 — Graphs: Connectivity, Matching, Colouring

Both statements are fundamental properties of undirected graphs, derived from the Handshaking Lemma:

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

• Statement Q is TRUE: Since the sum of the degrees of all vertices is equal to $2|E|$ (where $|E|$ is the number of edges), and $2|E|$ is always an even integer, the sum of degrees must always be even.
• Statement P is TRUE: Let us partition the vertices into two sets: $V_{\text{even}}$ (vertices with even degree) and $V_{\text{odd}}$ (vertices with odd degree). $$\sum_{v \in V_{\text{even}}} \text{deg}(v) + \sum_{v \in V_{\text{odd}}} \text{deg}(v) = 2|E|$$ Since the total sum ($2|E|$) is even and the sum over $V_{\text{even}}$ is even, the sum of degrees of odd-degree vertices ($\sum_{v \in V_{\text{odd}}} \text{deg}(v)$) must also be even. For a sum of odd numbers to be even, the number of terms ($|V_{\text{odd}}|$) must be even.

Thus, both statements P and Q are always true.