Since Leonhard Euler, Graph Theory has made amazing contributions to the world of mathematics and proofs are needed to validate reasoning. Without these proofs the whole study of graph theory would be based on speculation, but mathematics thrives on certainty. It would take books to contain all the proofs on graph theory, but here we will focus on two of Leonhard Euler’s propositions from ″The Seven Bridges of Konigsberg″. The first one is:
I note that the sum of all the numbers of bridges to each region ... is necessarily double the actual number of bridges... It follows that the sum of the [number of bridges to each region] must be an even number, since half of it represents the actual number of bridges. Hence it is impossible for exactly one of these numbers (indicating how many bridges connect with each region) to be odd, or, for that matter, three or five, etc. In other words, if any of the [number of bridges to each region] are odd, an even number of them must be odd (p 405-406).
This can be restated simply as: In a graph the number of odd vertices will always be even.
Informal Proof:
First, we need to prove what is called the handshaking theorem. This is because if a room full of people shook hands and each person counted the number of hands they shook, then every handshake would be counted twice. So let n be the number of people and so the ith person shakes hands di times. The total number of handshakes can be written as:
d1 + d2 + ... +dn-1 + dn
(Martin)
Written formally this means that the sum of all the degrees of each vertex equals twice the number of edges:
(Goodaire & Parmenter, 2006, p. 292)
A more formal proof of this can be found at the following website: MATours
Now since the handshaking theorem is proved we can now use it to prove the original proposition. So since ∑v ∈ V deg v = 2|E| is an even number we know that:
We know that the sum of all the even vertices must be even. It follows that the sum of all the odd vertices must also be odd. Now it is proven that if you add two odd numbers the sum will be even. Therefore for the sum of the odd vertices to be even, there must be an even number of odd vertices (Goodaire & Parmenter, 2006, p. 292).
∎
Looking at a second proposition from Euler’s we can prove the conditions for an Euler Circuit. This is when there exists a closed walk that includes every edge once and only once, and ends back at the same vertex it started from. Euler’s proposition was:
Thus for any configuration that may arise the easiest way of determining whether a single crossing of all the bridges is possible is to apply the follow rules...if there is no region with an odd number of approach bridges, the required journey can be effected no matter where it begins (p. 406).
This can be restated as a graph, with at least two vertices, has an Euler Circuit if and only if the graph is connected and each of the vertices has an even degree.
Informal Proof:
(→) Assume that a graph has an Euler Circuit. Now imagine tracing along the edges of a graph and starting at some point random point. There must be a connected edge to each vertex that your pencil can follow and each subsequent vertex must have an edge coming into and leaving it. This means that there must be an even number of edges connected to each vertex. The point that will be your starting and ending point can be visited more than once, but there must always be an edge leading to and from the vertex. Then in order for you to finally trace back to this vertex for the final time there must be one edge left untraced. This means that the vertex you both start and end on must have an even degree (Guichard, 2015, p. 69). Therefore if a graph has an Euler Circuit, then it must be connected and each vertex must have an even degree.
(←) Suppose that the graph is connected and all the vertices have an even degree. Start on any vertex in graph G, call it v0. Now if there are loops incident to v0 follow the loops first without repetition. Then there is at least two remaining edges to follow, because deg v0 is even and it is connected. So choose a vertex to follow. Let it be v0v1, which is connected to v1. At v1 fist follow any loops that are incident to it and then since v1 has an even degree we know the edges incident to it must be greater than zero and even. Therefore there is still a remaining edge that has not been followed, let it be v1v2. Now we know there exists a trail between v0 and v2, so at this point repeat these steps. Since each degree of each vertex is even there will always be a different edge remaining with which to leave that edge. Let this graph be finite, and so this process must end at some point. So eventually we must arrive back at v0, which is possible because it has an even degree. Let this be a circuit, call it C1. If all the edges of v1 have been used than this process is finished and the graph has an Euler circuit namely C1. Now repeat this process starting again at v1 till there is a new Circuit formed, namely C2. We see that C1 and C2 are connected, so therefore there exists and Euler Circuit. If there is no remaining edges, then we are done. If not repeat this process, and since our graph is finite, this must eventually end when all the edges have been used in the circuit (Goodaire & Parmenter, 2006, p. 307). Therefore there exists an Eulerian circuit.
∎
This can formally be proved with induction with a more detailed proof that can be found at the following website: An Introduction to Combinatorics and Graph Theory