24.1.6. Handshaking Theorem

Next, we state a very fundamental fact about an undirected graph this is also called as the handshaking theorem. So, if you are given an undirected graph it may be simple, it need not be simple, it is just an undirected graph. And say the graph has m number of edges. Then what the theorem basically says is that if you sum the degrees of all the vertices in the graph then it will be twice the number of edges always.

The Handshaking Theorem states that in any undirected graph, when you add up the degrees (the number of connections) of all the vertices, the total will always be twice the number of edges. This happens because each edge connects two vertices, and thus contributes to the degree counts of both vertices involved. Therefore, every edge is counted twice in the total degree sum.

Imagine a party where each guest (vertex) shakes hands (edges) with other guests. If you count every handshake made by each guest, you'll find that handshakes are counted for both participants. So if there are 10 handshakes in total, the degrees (the total number of handshakes counted) will sum to 20, since each one is counted for both guests.

So, you can verify this with respect to this example graph, so you take the summation of ∑(deg(v1)) + deg(v2) + deg(v3) = 2m.

To apply the Handshaking Theorem, you would summate the degrees of each vertex in a graph. For example, if you have three vertices (v1, v2, and v3) with degrees deg(v1), deg(v2), and deg(v3), then the total degree sum will be 2 multiplied by the number of edges (m). This allows you to find either the total number of edges or verify the number of edges if all vertex degrees are known.

Think of a sports team where players (vertices) have assists (edges). If one player assists 2 times, another player 4 times, and another 6 times, the sum of assists is 12. According to the Handshaking Theorem, all assists have actually contributed to 6 interactions (edges), because each assist is counted for both the player making the assist and the one receiving it.

So, consider any arbitrary edge e = (u, v) in your undirected graph. The claim is that the contribution of this edge will be 2 to the overall summation of degrees of all the vertices.

Each edge in an undirected graph connects two vertices and contributes to the degree count of both. For example, if you have an edge connecting vertex u and vertex v, when calculating degrees, it adds 1 to the degree of u and 1 to the degree of v. This means that each edge effectively adds 2 to the total degree count across the graph.

Think of each handshake again. If two friends shake hands, they both count that handshake in their record of how many handshakes they've made. If we had just one handshake (edge), each friend counts it as one, making a total contribution of 2 when we tally it up.

Hence it is easy to see that the summation of the degrees of all the vertices will be twice the number of edges in the graph.

In conclusion, after accumulating the contributions of all edges, the total number of degrees will always equal twice the number of edges in the graph. This illustrates the relationship between edges and vertex degrees. This theorem can be extremely useful in various applications, such as network analysis or graph coloring, as it provides insight into the structure of the graph.

Consider a social network where each connection represents a friendship (edge). If there are 5 friendships total, each counting for two people, that reflects how 10 people might have an average of 2 connections each. The Handshaking Theorem helps us confirm that the connections (edges) are consistently reflected in how we view the friendships (degrees).

--