Hi. In this video, we're going to consider two problems about connecting points. And actually, I assume that you have just worked on two interactive quizzes that were prepared for you, and those quizzes contained two problems. One of them about 10 points and connecting them with segments and another one about nine points. If you haven't yet tried to solve those quizzes, I encourage you to go back and first try to solve them and then return and hear this lecture, because we're going to discuss the solutions to those problems and it is very useful to first try to solve problem yourself before hearing and discussing the solution. So the first problem goes like following, we have 10 points on the plane. They're arranged in a beautiful symmetric manner like a circle, and you need to connect some of these 10 points with segments, like two pairs of points which are connected on this picture. Such that every point is connected exactly with five other points. The solution for this problem, is also beautiful and symmetric. The idea is, we can separate the points into the left half and the right half with this vertical line and each half has exactly five points. And now, what we need to do, is to connect each point from the left half to each point of the right half, and we will get such picture, which is beautiful and symmetric but the main thing is that this is the solution to our problem, because for every point in the left half, it is connected exactly to five points from the right half. And for any point in the right half, it is connected exactly to the five points from the left half. And the points in the left half and in the right half are not connected between themselves. So, for all 10 points every point is connected with exactly five points as needed. So this is one of the possible examples. I'm sure that some of you came up with other examples, but it is sufficient to show just one example for this problem. And now, we move on to a very similar problem about nine points. Now you are given nine points instead of 10. They're also organized in this symmetric circular manner and you also need to connect some of them with segments, so that each point is again connected with the five other points. Now we ask you is that possible at all? So, to solve this problem, we first need to introduce some definitions. Numbers from zero and integer numbers starting from zero, two, four, six, eight and so on are called even, and all the other positive integers starting from one, three, five, seven and nine are called odd. So all even integers are going with the difference two between them and all the odd integers are going with difference two between them. All even numbers are divisible by two, meaning that if you divide any such even number by two, you will also get an integer number and all the odd numbers are not divisible by two. Now, we are going to call points A and B neighbors in this particular problem if A and B are connected for the segment. So in our problem with nine points, some of them will be connected by segments, some of them won't be. If two points are connected with the segment, they are called neighbors, and if B is neighbor of A then A is also a neighbor of B. This is symmetric. Now we're going to define even and odd points. So let us call a point even if it has even number of neighbors, otherwise we call this point odd. So, looking at this particular picture with nine points and some of them are connected with segments, how many odd points and how many even points are there? So the answer is that there are exactly four odd points, and those are A, B, C and D, because each of them is connected to just one other point, and so the number of neighbors for A, B, C and D is one and one is odd number. So points A, B, C and D are odd points. All the other points are even. Points E and F have no neighbors, so they have zero neighbors and zero isn't even number, so E and F are even points, and points G, H and I are all connected to each other and so each of them has exactly two neighbors and two is also an even number. So G, H and I are also even points. Now, I state theorem that the number of odd points is always even regardless of how many points are there, and how many segments are there, and which exactly points are connected and which points are not connected by segments. That all doesn't matter. In any case, the number of odd points is always even. So a number of odd points is either zero or two or four or six and so on. And we're going to prove this theory now. The idea of the proof, is very similar to the idea from the previous video. We start with the obvious statement that when there are no segments, there are no odd points because no points have any neighbors, so every point has exactly zero neighbors and so every point is even. And, to go to the general case when we have some points connected with segments, we can actually start with the situation when there are only some points and no segments, and then we add segments one by one. The key idea is that when we add segments one by one, the number of odd points either doesn't change at all or increases by exactly two or decreases by exactly two. And thus the number of odd points, if it was even some point, it stays even, because when you don't change a number or change it by plus or minus two, it remains even. This is the idea and now, let's go through and prove it. So the easy case is when there are some number of points and it doesn't matter how many points, and there are no segments. Then each point has exactly zero neighbors, and so there are no odd points. And so, the number of odd points is zero. Zero is an even number so there is indeed even number of odd points. So we have proven this simple case. As you remember, this is called induction base and we'll use this for our proof. Now, we need to also prove the induction step, and to do that we need to consider what happens when we add segments. Let's start with nine points and try to add some random segments and see what happens. So when we start, the number of odd points is zero because there are no neighbors and so each point is even. What happens when we add segment A and B? Well, it connects points A and B, and now point A has one neighbor and point B has one neighbor, so A and B become odd points. And before we ended segment AB there were no odd points, and now, there are two odd points. So the number of odd points increased by two. And now we have exactly two odd points, and all the points other than A nd B are still even. Now, let's try adding segment HI. It again adds two odd points H and I, because it connects H and I to each other, and now, both of them have exactly one neighbor. One is an odd number. And so H and I are now odd points. And so again, we increase the number of odd points by two and the total number of odd points is now four. Now what happens if we add segment BC? Now something different happens, because B was odd before adding this segment and C was even. Now when we add segment BC they switch. Now B is even and C is odd. Why is that? Because B now has two neighbors A and C, and so B is an even point now, and C has only one neighbor B and so C is an odd point. And in this case we added one odd point and removed one odd points so the number of odd points didn't change. We again have four odd points, and those are A, C, H and I. Now we want to add segment A, C. And this will make both points A and C even, because now A has two neighbors B and C, and C has two neighbors A and B, and so A and C now are even and they were odd. So we have just decreased the number of odd points by two, and now we have only two odd points and those are H and I. So you see what happens, for any segment in this example at least when we added it, it either doesn't change the number of odd points or it increased the number of odd points by two or it decreased the number of odd points by exactly two. Now, let's consider what happens when we're adding a segment in general. And again, we're going to focus only on the two points which this segment connects. The same way as we focus on the triangle that existed in the previous video. Why is that? Well because when we add a new segment from point A to point B, then all the other points don't change. The number of neighbors for all that other points doesn't change. And so the number of odd points among all the other points, also doesn't change. The only thing that changes is maybe the oddity of point A and the oddity of point B. And now we consider several cases, first case is, when before adding segment A, B. A and B were even points, then A, B makes them both odd because A and B both had even number of neighbors, and now, both of them have by one neighbor more, and so, those even numbers after adding one to them became odd and so A and B, now both have what number of neighbors and so A and B are now odd points. They were even, they became odd, so we added two more odd points in this case. Now, the second case is if A and B were odd before adding segment A, B. In this case, adding A, B makes them both even, because they had odd number of neighbors. Now they have each one more neighbor. If you add one to an odd number, you get an even number. And so A and B now have even number of neighbors. And so A and B are now even points, so they were odd, and now they're even, so we removed A and B as odd points so we removed exactly two odd points. And the third, case is when A is even and B is odd before adding segment A, B. In this case, adding segment A, B swaps them. A becomes odd and B becomes even because A was even, it has even number of neighbors and after adding segment A, B, it has one more neighbor, and so it becomes odd. And for B, it's vice versa, it was odd, we add one way number and becomes even. And so we removed one odd point and we added one odd point and so the total number of odd points stays the same. And the fourth case, would be when A was odd and B was even before adding segment A, B but this is actually symmetric, and in this case also the number of odd points stays the same. So what we see is that after adding a segment in general, the number of odd points always either increases by two or decreases by two or stays the same.
