Hello, and welcome to the next module of the graphs class. We started with a well known handshaking lemma. Before stating this lemma formerly, let's revisit the following passage. We're given 9 points. And we would like to connect some pairs of them by segments so that each point is connected to exactly 5 other points, okay? So try to understand whether it is possible or not. Let's just start connecting points by segments. So, for example, if we connect these 2 points by segment, then each of them now is connected to exactly 1 point. Now lets add 1 more segment. That way we have 2 more points of degree 1. Then another sigma, then now we have a point of degree 2. But what is essential in this case is that the number of points who's degree is odd always stays even, okay? Now let's just try to realize that in this case we have 4 points of odd degree, right? So this number is odd. Now, let's add another segment. In this case, what we get is that we get 2 new points of odd degree. Now the number of points of odd degree is equal to 6, which is still an even number. Now, let's add another segment. Now these two guys are of degree to line 4, which is even. So all the points of 4th degree are this ones, and its number is 4. So as you see, the number of points of 4th degree always stays even. So it is even in the beginning when it is equal to 0. And then each time when we add a new segment, it either stays the same, or it increases by 2, or it decreases by 2. So it always stays even. And this is essential for this problem, because it actually proves that our mission is impossible, in this case. Because if we reach the situation when there are 9 points and all of them have degree 5, then this means that the number of points of odd degree is odd in this case. But we've just shown that it always stays even. And this actually formally proves that this task is impossible. And in a more general setting this is known as a handshaking lemma. The real life statement of this lemma is by following, so before a business meeting some of its members shook hands. Now what we claim is that the number of people who shook an odd number of hands is always even. In graph terms it is stated as follows, in any graph, the number of vertices of odd degree is always even, okay? And this is actually, it can sequence of the following degree sum formula, which states the following. If you have an undirected graph, and if you compute the sum of degrees of all its vertices, then what you get is exactly twice the number of edges, right? So the question is how it implies the handshaking lemma. Well, it implies it as follows. So if we had an odd number of vertices of odd degrees, then the sum of all degrees would also be odd. Why is that? Well, we have some number of vertices of even degrees. So the sum of their degrees is, of course, even. This is just some number of even numbers. Their sum is always even. And then we also have some number of vertices of odd degree. If this number is odd, for example, we have something like 1, 3, and 5, then the sum of these numbers is odd. So the total degrees, the sum of all degrees, is some even number, plus some odd number, which gives them odd number. So what we would get is that 2 times E is even to some odd number, which cannot be the case, of course, right? Because 2 times E is always an even number, right? Now let's prove the degree sum formula. So, before proving, let's consider a point example. We will actually use this point example to prove the formula. So this is a graph with 6 vertices and 8 edges. And all the degrees of the vertices are shown here. And, indeed, if we compute the sum of all the degrees, it is 3 + 5 + 3 + 2 + 1 + 2. It gives us 16, which is exactly 2 times the number of edges, 2 times 8, okay? Now let's try to prove the formula. For this, let's do the following. Let's temporarily remove all the edges from our graph. Now the degrees of all vertices are equal to 0, and the number of edges is also equal to 0. So, in particular, our formula works for this simple graph, because the sum of all degrees is 0 and twice the number of edges is also 0. So 0 is equal to 0, so we are in good shape in this case. Now let's start adding edges back, one by one. So each time we add a new edge, we also update the degrees of the two corresponding vertices. So now we have just edge and two vertices of degree 1. In particular, note that in this case our formula still works. So if the number of edges is once or twice, the number of edges is equal to 2. On the other hand, the sum of all degrees is also equal to 2, okay? Now we can continue this process until we get our initial graph, okay? So this is our initial graph. Now it is important to understand the following. Each time when we add a new edge, first of all, the quantity 2 times e always grows exactly by 2, right? Just because when we add an edge, e grows by one which means that 2 times e grows by 2. On the other hand, when we add a new edge, the total degree, namely the sum of all degrees, also increases by 2, right? This is just because when we add an edge, we increase the degree of this vertex by 1 and of that vertex by 1. So we have two quantities, the sum of all degrees, and twice the number of edges. Initially, they are both equal to 0. Then, we start adding edges. And each time, when we add a new edge, this one increases by 2, and this one increases by 2. So they always stays the same, okay? So what just happened is that we proved the degree sum formula by induction on the number of edges. Our base case was an antigraph, a graph without any edges, right, when the number of edges is equal to 0. In this case, the formula holds for three reasons. And then, what we've proved as an induction step, we've showed that each time when we add a new edge, we increase the total degree by 2. And we increase by the number of edges also by 2, which finally proves us degree sum formula, once again.
