We will now use graph theory to solve another toy puzzle,

and to introduce some new important concepts.

There were 20 students at an exam and each of them solved exactly three problems.

It is also known, that each problem was solved by exactly five students.

The question is, what was the number of students,

what was the number of problems, I am sorry, at this exam.

First of all, let me show you that in fact we did

not need graph theory to solve this puzzle.

Indeed. To solve it,

assume that each student wrote each

of his or her three solutions on a separate piece of paper.

Then we conclude that there were exactly 60 pieces of papers,

so exactly 60 solutions.

Let us now take all the 60 solutions and stack up all the solutions of the same problem.

We will organize our solutions into piles,

so each of our piles contain solutions that are exactly the same problem.

We know that there are some number of piles,

the number of piles is exactly the same as the number of problems,

and we also know that in each pile the number of pieces of paper is equal to five,

because for each problem there are exactly five solutions.

We have some number of piles,

in the pile there are exactly five pieces of paper,

and the total number of pieces of paper is equal to 60,

which means that the number of piles is equal to 60 divided by five.

That is just 12.

The number of problems is 12, so this is the answer.

As you see we do not need graph theory.

At the same time, let me show you that it is natural to use graphs here.

To construct the graph here,

let's introduce a node for each of our 20 students.

They are shown here on the left.

On the other hand, let's introduce a node for each of our problems.

Let's pretend that at this point we still do not know

the number of problems and let to node them by K,

the number of problems by K.

Now, let us do the following,

let's connect each of our 20 students with

three problems that were solved by this student.

For example, this bottom student solved the following three problems,

some other student solved the following three problems.

In general, the picture looks as follows and in fact,

the exact structure of the graph is not so important for us.

What is important for us,

is that this is bipartite graph,

so each edge in our case joins a node on the left with a node on the right.

This allows us to compute the number of edges in two different ways.

On one hand, we know that the number of edges is equal to 20,

which is the number of nodes on the left,

times three, just because the degree of

every node on the left is equal to

three and we know that each edge goes from left to right.

Well now is a hint, we can do the same with the right part.

We know that on the right,

we have K nodes and the degree of each of these nodes is equal to five,

which means that the number of nodes is equal to 5 x K. We have this equality

60 = equal 5 x K and we conclude that K is equal to 12.

Now let me take this chance to introduce the required concepts.

First of all, as I mentioned over these,

the results in graphing is bipartite.

Just by definition a bipartite graph is a graph whose nodes can be

partitioned into two parts such that in each of

these parts there are no nodes, there are no edges, I am sorry.

Every edge joins some node from the left part with some node from the right part.

This is bipartite graph by definition.

In this graph, we used the technique known as double counting to solve our problem.

Namely, we counted the number of edges in two different ways.

On one hand, we showed that the number of edges in

such a graph is equal to the total degree of the left part,

where the total degree is just the sum of all degrees,

of the vertices, of the node on the left.

On the other hand, by exactly the same argument,

it is equal to the total degree of all the nodes on the right.

This allows us, finally,

to compute the number of nodes in the right part.