3. The key behind this proof is to add up all the numbers in the incidence matrix in two different ways. Let the sum of all the entries in the incidence matrix be S.
| The sum of the entries in the row corresponding to vertex vi gives the degree of vi. Therefore, the sum of all the rows will give | n | deg(vi) | = |
S. |
| S | ||||
| i=1 |
Furthermore, since every edge has exactly two endpoints, summing the entries in each column will give 2. Therefore, the sum of all the columns will give 2e = S.
| Hence, | n | deg(vi) | = |
2e. |
| S | ||||
| i=1 |