What is a Graph? · Degree Sum Formula

Lesson 5

Nikolai Chukhin · Alexander S. Kulikov

Assume that each student wrote a solution on a separate piece of paper. Then, there are \(20 \times 3 = 60\) pieces of paper. For each problem, let us stack up all its 5 solutions. Then, the number of piles is equal to the number of problems. Thus, the number of problems is \(60/5=12\).

In graph terms, this solution can be stated as follows. Denote the number of problems by \(k\) and consider the following bipartite graph: one part is \(20\) students, the other part is \(k\) problems, and there is an edge between a student and a problem if this student solved this problem. Hence, the degree of each student is equal to three, whereas the degree of each problem is equal to five.

Now, we use the double counting technique to estimate the number of edges in this graph. On the one hand, the number of edges is equal to the total degree of the students which is \(20 \times 3=60\). On the other hand, it is also equal to the total degree of the problems which is \(5k\). Thus, \[k=\frac{60}{5}=12 \ .\]