Use of Handshaking Lemma to find number of subarrays with even Sum

Question

I was attempting to do practice questions and came across a solution I do not understand the reasoning behind.

The question can be found here, finding the number of even sum subarrays. https://www.geeksforgeeks.org/find-number-subarrays-even-sum/

Questions related have been asked, but I am asking specifically about the use of the handshaking lemma at the end of the solution.

I understand that we build a count of the even and odd sum subarrays, but do not get why we use the hand shaking lemma to compute the number of even sum subarrays. If we get a count of even and odd cumulative sums, how does the handshaking lemma exactly play into this? Clearly, an even sum subarray is made of either odd + odd, even + even, or a lone even value, so I would just like to know how exactly all cases are being accounted for in this specific scenario. Thanks for your help!

Answer 1

First we have an array of numbers, for example:

[1,3,5,2,10,7]

So, how to count the number of subarray with even sum? Let's convert it into another array called sum, which the value at index ith is the sum of subarray from 0 to ith index

[1,4,9,11,21,28]

Clearly, we can see that for a subarray from range a to b, the sum of this subarray is even if and only if sum[b] - sum[a - 1] is even.

Now, let imagine that a graph connecting between odd and odd entry in sum and even and even in sum -> the number of edges in this graph is the answer for this problem.

So, from the handshake lemma, 2*E = sum of all vertexes degree

• The degree of each odd vertex is number of odd vertex - 1

• The degree of each even vertex is number of even vertex - 1

=> so

2*E = odd*(odd - 1) + even*(even - 1) => E = odd*(odd - 1)/ 2 + even*(even - 1)/2

Another way to understand this is for odd entries, the number of ways to choose odd - odd pairs is C(odd, 2) = odd*(odd - 1)/2 with C is the combination