Friday, February 12, 2016

Sum of the Squares of the Degrees

One of the most fundamental results in graphs is that the sum of the degrees of all the vertices of a graph is twice the number of edges in it.


This is is the famous Handshaking Theorem.
It is called Handshaking Theorem due to the analogy of the involvement of two hands in every handshake with that of the two vertices in every relation (edge).

Hence, the total number of relations of the persons (degrees of  the vertices) in a graph is double the number of relations (edges) in it.

What happens if we add the squares of the degrees of all the vertices in a simple graph?

It is found out that the sum of the squares of all vertices in a graph is the the sum of the degrees of the adjacent vertices of all the vertices the graph it self.


Why is it so? It is because, the square of the degree of a vertex is same as adding the degree of a vertex, the degree number of times.
                                                         n2=n+n+n+...+n (n times)
But one can easily verify that every vertex has exactly its degree number of adjacent vertices. Hence, when we sum the degrees of  the adjacent vertices of all the vertices of a graph, every degree is added that degree number of times. This proves the result.

We can also observe that if we add all the degrees and degree squares of all the vertices of a graph, then it is same as summing up all the degrees of all vertices in the closed neighbourhood of all the vertices of that graph.

No comments:

Post a Comment

Develop a skeleton for each day

One has to develop one's own habit of writing. One important  characteristic of habit is that one may not realize what one does in a hab...