24.1.7. Euler's Theorem

Based on this fundamental fact we can derive another conclusion about any undirected graph and this conclusion is often called as the Euler's theorem. So, what it says is the following. So, what this theorem basically says? It says that you take any undirected graph then the number of vertices of odd degree will be always even.

Euler's theorem pertains to the structure of undirected graphs. It states that in any undirected graph, if you count the number of vertices (nodes) that have an odd degree (which means they are connected to an odd number of edges), you will always find that this number is even. This means you cannot have 1, 3, 5, etc., vertices with an odd degree; you can only have counts like 0, 2, 4, etc. This property arises from the earlier discussed concept that the sum of all vertex degrees in the graph is twice the number of edges, which is an even number. Hence, if some vertices have odd degrees, they must pair up to maintain overall evenness.

Imagine a group of friends with connections to each other, where each friend represents a vertex and a connection between friends represents an edge. If a friend has an odd number of connections (say they directly know 3 friends), they will be left out from pairing with another friend who also has an odd count, leading to an unbalanced situation. However, every 'odd connection' must pair up, resulting in always having an even group of friends with odd connections, much like how the odd-degree vertices must pair up.

For that deriving this conclusion we will use the previous fact namely the summation of the degrees of all the vertices in the graph is twice the number of edges and the proof is very simple. So, let V be the set of vertices in your undirected graph...

The proof of Euler's theorem relies on understanding that the sum of degrees of all vertices is even because it equals twice the number of edges (edges contribute two times: once for each vertex it connects). Since each vertex can only be either of odd or even degree, you can categorize them. By partitioning the vertices into two groups (those with odd degrees and those with even degrees), you observe that the total degree must remain even. If the total contribution from the odd-degree vertices is odd, you cannot maintain the even total, leading to the conclusion that you cannot have an odd number of odd-degree vertices.

Think of a dance party where friends are connected by pairs (partners). If there's an even number of friends dancing, they can all pair off perfectly. However, if an odd number of friends, say 5, tries to dance, one friend will always be left out (no partner), leaving us with unpaired vertices of odd degrees. Thus, to maintain an even pairing situation (a proper dance), the dancers must come in pairs, reflective of having an even number of odd-degree friends.

So, because you are summing up several odd quantities and the summation of those odd quantities is even. That is given to you, that is possible only when the number of quantities that you have added is even. So, that is a fundamental fact about any undirected graph...

From the earlier observations, we conclude that in undirected graphs, the outcomes of odd-degree vertices must always balance out to retain the even sum of edges. Thus, after analyzing various properties of graph connections, Euler's theorem gives a fundamental property that can help understand the structure and arrangement of edges and vertices better.

Consider a street intersection as a graph where streets (edges) meet at junctions (vertices). If some streets start and stop at odd junctions, ultimately there must be an even number of them so that traffic can flow smoothly without any vehicle being left alone making unnecessary detours or hanging out at odd junctions.

--