A graph consists of objects called vertices and connections between them called edges. For every vertex, we can count how many neighbors it has, which is called its degree. In the following video (in Dutch), Prof. Remco van der Hofstand explains why the degrees in a graph play such an important role!
In the basic notions, this is explained in more detail. In this article, we discuss simple graphs, meaning that there is at most one edge between any pair of vertices and there are no self-loops that connect a vertex to itself by an edge.
Dutch railway network and the degree histogram. The degree of a station corresponds to the number of other stations that are directly connected railway to the station. Picture of the railway network was done by Dennistw (Own work) [CC BY-SA 4.0 (http://creativecommons.org/licenses/by-sa/4.0)], via Wikimedia Commons.
The degrees of vertices are very interesting. For example, in a friendship network, the degree of a person is the number of friends the person has. In a railroad network, the vertices are stations and there is an edge between two station when they are connected by a railway line. In a railroad network, the degree of a station could be the number of railways that link that station to other stations. In a scientific collaboration network, the vertices are scientists and we draw en edge between two of them when they have written a paper together. Then, the degree of a scientist is the number of other scientists she/he has written papers with. Thus, the collection of degrees of all the vertices in a graph gives us a lot of information about the graph.
It is fairly obvious that not all sequences of degrees are possible. For example, the degree of any vertex in a graph is always smaller than the number of vertices in it, since each of the other vertices can be in at most one edge with it. Since the number of other vertices in the graph is the total number of vertices minus one, the degree of any vertex is smaller than the total number of vertices in the graph. There is another very simple restriction on the degrees that is true in any graph, and that is sometimes called the handshake lemma. The handshake lemma states that the if we compute the sum the degrees over all the vertices in the graph, then we arrive at an even number. In fact, it is equal to twice the number of edges in the graph. In a mathematical formula,
total degree of all vertices = 2 x total number of edges
This is called the handshake lemma, since if we model whether pairs of people have shaken each other’s hands as a network, then the sum of the number of handshakes over the people is again an even number that equals twice the number of handshakes. The handshake lemma is even true in cases where pairs of people can shake each other’s hands arbitrarily often. How can we see that the sum of the degrees in a graph equals twice the number of edges? Well, looking at some simple examples certainly helps. When we only have one edge in the graph, it means that all degrees are zero except for the two vertices that are in the end. Thus, the sum of the degrees equals two, which indeed is twice the number of edges in the graph. However, this is only a very simple example. Try it yourself in the simple network in the figure below:
The general case is only slightly more difficult. What we can do is show that if we add an edge to any graph, then the sum of the degrees goes up by precisely two. Then, we get our statement by adding edges one by one. For each edge, the sum of the degrees goes up by two. In the empty graph, the sum of degrees and the number of edges are both equal to zero, so that the formula total degree of all vertices = 2 x total number of edges clearly holds there. If the sum of the degrees goes up by two for each edge, we then get that the general formula holds for every graph and every number of edges. So, how does the sum of the degree change when we add one edge to a graph? Well, the degrees of the two vertices that make the edge that we are removing each go up by one, all other degrees remain the same. Summing out, we see that the sum of the degrees goes up by two. We conclude that the formula
total degree of all vertices = 2 x total number of edges
holds in general.We have now seen what the degrees in a graph are, and have formulated two simple properties that such degrees must satisfy: no degree can be larger than or equal to the number of vertices in the graph, and the sum of degrees needs to be even. In the next part, that will follow soon, we further investigate degrees in graphs.
How are elements in real-world networks connected? That is the question we aim to answer in this post. Most real-world networks turn out to be extremely inhomogeneous.
A mathematician once told me that problems that are very simple to state can be very deceiving, and sometimes turn out to be extremely difficult to solve. One such problem was the Four Color Problem.
A conjecture of Erdős and Hajnal from 1989 says that forbidding any specific substructure results in existence of a very large homogeneous one! In this article you will have a look into one of the most fascinating problems in modern graph theory.
![Dutch railway network and the degree histogram. The degree of a station corresponds to the number of other stations that are directly connected railway to the station. By Dennistw (Own work) [CC BY-SA 4.0 (http://creativecommons.org/licenses/by-sa/4.0)], via Wikimedia Commons](https://networkpages.nl/wp-content/uploads/2016/11/NLRailWithDegreeHistgram1024-1.jpg)
