[MUSIC] Now we're ready to proof the whole statement about points that always regardless of number of points, and number of segments, and which points are connected, and which are not, the number of odd points is always even. The proof structure is the following, first we prove that when there are no segments, then disregarding number of points, the number of odd points is always even. Because actually the number of odd points is 0 and 0 is even. So for 0 segments, we have proven our theorem. Now we're going to do induction based on number of segments and we're going to make a step from 0 segments to 1 segments. We assume that for 0 segments, the number of odd points is always even. And we prove that in that case, for any one segment, if there are some number of points and exactly one segment connecting to some pair of points, the number of odd points is also even. And to do that, we use the fact that when we add a segment, the number of odd points if it was even, it stays even. And we know that it was even with 0 segments. So after adding this 1 segment, it stays even. And so we now know that for 1 segment, our theorem is also true, because we know that for 0 it is true, and assuming that for 0 it is true, we have proven that for 1 it is also true. And so 1 we can go from 1 segment to 2, because if we want to do something for two segments, we can choose one of them to be the first one. And then we know that if we just add only this first segment then number odd points will be even. And then after we add the second segment on top of it, the number of odd points will stay even, so for any 2 segments the number of odd points is also even. And then we can make the step from 2 to 3, and so on. But we want to make all the way to n, and to do that we prove the general thing, that if for some k, for any case segments connecting some number of points, number of odd points is always even. And then for any k + 1 segments and any number of points connected by those k + 1 segments, the number of odd points will also stay even. And this step can prove be proven in the same way. We know that in the general case when we add a new segment, the number of odd points stay the same or is increased or decreased by 2. So if it was even, it stays even. And given this induction step from k to k + 1, we can make the step from 3 to n. And actually we could skip all those intermediate steps from 0 to 1, from 1 to 2 and so on. We could just prove that for 0 segments, our theorem is true. And the step from k to k k + 1 in the general case. And that would already allow us to go from 0 to any n. And actually, we can skip all those intermediate steps and just prove the induction base for n = 0. Prove the induction step from n to n + 1. And we get the profit, we have proven our theorem. Now let's remember, why did we need this theorem? We had a problem about 9 points. We had 9 points and we wanted to connect some of them with segments in such a way that every point has exactly 5 neighbors. So let's suppose we succeeded, and then all 9 points would be odd because each of the 9 points has 5 neighbors. 5 is an odd number and so the point is odd and so all 9 points are odd. But then, the number of odd points will be 9. But we know from the theorem that for any configuration of segments, the number of odd points must be even. And 9 is not even, so it is impossible. And indeed, for 9 points it is impossible to find a solution. So for ten points we have shown an example how to connect them in a nice symmetric way so that each point has exactly five neighbors. But for 9 points it isn't possible. We could try proving it by drawing every possible combination of segments for 9 points and showing that it doesn't satisfy our requirement that there is at least one point that doesn't have exactly 5 neighbors. But, instead of doing that, that will take a ton of time. Instead of doing that, we have proven using mathematical induction some supportive statement about the number of odd points that it is always even. And then based on that, we proved that this problem cannot be solved. And in the next video, we're going to talk about famous mathematician, and a problem that his teacher gave him in school. [MUSIC]