Recommendation: you can either first go over the glossary to comprehend the terminologies, or directly go through the results and refer to the glossary along the way. Also, you can take some scratch paper to visualize some of the contents yourself.
Let's first tackle the classic Königsberg's bridges problem.
- Theorem 1
Proof First we prove the "only if"(\(\Rightarrow\)) part. That is, the presence of a closed Eulerian trail implies that all vertices have even degrees.
In fact, take a closed Eulerian trail(call it W) and let A be a vertex that's not the starting(also ending) point of W. Assume that A is visited \(a\) times by W. Because each time the trail enters A, it has to exit, there are \(2a\) edges in connection with A. Since the Eulerian trail uses every edge in a graph, A has a degree of \(2a\), which is even. Now, say B is the start and the end of W. If B is visited exactly \(b\) times between the start and the end, the degree of B would be \(2b+2\) where the +2 comes from the start and end. So indeed every vertex has an even degree.
Then, we prove the "if"(\(\Leftarrow\)) part. Assume every vertex has an even degree. Take any vertex S, and start walking along on edge \(e_1\) to \(A_1\), and walk along any new edge \(e_2\) from \(A_1\). Repeat this process, until a closed trail \(C_1\) is formed. Note that since G is finite(universal assumption unless specified otherwise), such a \(C_1\) always exists. If \(C_1=G\), we are done; else, choose a vertex \(v_0\) in \(C_1\) such that \(C_1\) doesn't contain all edges incident at \(v_0\).
Remark: such a vertex always exists. Suppose \(C_1\) has all edges connecting to all vertices in it. As \(C_1 \ne G\), \(C_1\) has fewer edges than G, so there is some vertex A that's not in it. However, because G is connected, there is a path from A to a vertex of \(C_1\). So start walking on this path, and the moment you reach \(C_1\)'s vertex(say V), the most recent edge is connected to V but not in \(C_1\). Contradiction.
So let's remove all edges of \(C_1\) from G, and we obtain a graph with all even degrees again(because at the beginning all degrees are even, and by removing a closed trail, we have removed an even number of edges on each vertex). Now, start at \(v_0\), take another closed trail in what's left(call it \(C_2\)). Thereafter, we can unite \(C_1\) and \(C_2\) by first walking by \(C_1\), stopping at \(v_0\), and then completing \(C_2\), coming back to \(v_0\), and finishing the rest of \(C_1\). If \(C_1 \cup C_2 = G\), we are done. Else, repeat the process above and it will eventually stop(again, because G is finite), meaning a closed Eulerian(using every edge) trail has been formed on G.
\(\Box\)
So what can we say about the bridges now...
Now we will look at a pertinent result.
- Theorem 2
Proof Add a new edge joining S and T and call the new graph H.
Claim: H has a closed Eulerian trail \(\Leftrightarrow\) G has an Eulerian trail starting at S and ending at T.
Proof of the claim: left as an exercise for the readers(hint: fairly trivial--just follow the structure of the proof above).
The theorem then follows from Theorem 1(as now in H \(deg(S)\) and \(deg(T)\) are even).
\(\Box\)
The following theorem illustrates a fundamental result that's cohesively utilized in many other scenarios.
- Theorem 3
Proof Take such a graph with \(e\) edges. Let \(d_1, d_2,..., d_n\) be the degrees of the n vertices of G. Now it's time to introduce a lemma.
Lemma \(\sum_{i=1}^n d_i = 2e\).
Proof of the lemma: on the left hand side, each edge is counted twice(each time by one of its two endpoints). \(\Box\)
So if G has an odd number of vertices with odd degrees, the sum of degrees would also be odd but it's equal to \(2e\). Contradiction.
\(\Box\)
Imagine the following scenario: your year group is holding an end-of-year party and there will be a round-table dinner. Everyone will sit somewhere around the table. Is it possible that all participants have their friends sitting next to them? Well, the following result could assist you in determining that.
- Theorem 4
Proof First note that G must be connected since otherwise, it would have a component of less than \(n/2\) vertices(but why is that?), meaning the vertices in that component have degrees smaller than \(n/2\).
Assume that G doesn't have a Hamiltonian cycle. Let's add new edges to G(anywhere) as long as we can without creating a Hamiltonian cycle. When we stop adding, we have a new graph, call it G'. All vertices in G' have similarly degrees at least \(n/2\) and there's no Hamiltonian cycle. Again, at this stage, adding any new edge would induce a Hamiltonian cycle.
Let P be a path of maximum length in G'. It's true that P contains all vertices of G'. Indeed, let x and y be vertices in G' such that xy is not an edge of G'. As adding the edge xy would induce a Hamiltonian cycle, it follows that G' has a Hamiltonian path(encompassing all vertices) from x to y.
By our condition, \(deg(x)+deg(y) \geq n\). Claim: there exists some \(i\) where \(2 \leq i \leq n-1\), and both \(xz_i\) and \(z_{i-1}y\) are edges of G'.
Proof of the claim: Assume otherwise. Then, if y has \(k\) neighbors, x has at most \(n-(k+2-1)\) neighbors(but why is that?). Thus, \(deg(x)+deg(y) \leq n-1\). Contradiction with our condition.
Now, the sequence \(xz_2...z_{i-1}yz_{n-1}...z_ix\) is a Hamiltonian cycle. Contradiction.
\(\Box\)
The following image illustrates the main idea of the proof, although the labels have some disparities.
You can interact with the following embedment: attempt to create a Hamiltonian cycle by clicking on the vertices one by one. Note: this animation isn't a visualization of Theorem 4, but rather highlights the logic that if G is Hamiltonian, it's not necessarily true that all vertices of G are of degree at least the order of G over 2. That is, the lower-bound condition is sufficient for a Hamiltonian cycle to exist, but not necessary.
Notice that everything we have covered so far is related to graphs in which edges have no directions. Every edge is analogous to a two-way street. Now, we are going to add directions to(orientate) graphs.
- Theorem 5
Proof First let's prove the conditions are necessary(\(\Rightarrow\)): as a closed Eulerian trail leaves and enters each vertex the same amount of times, G must be balanced(by definition). Meanwhile, such a trail provides a trail(path) from any vertex to any other vertex, so G must be strongly connected.
Then let's prove the conditions are sufficient(\(\Leftarrow\)). This would resemble the proof of Theorem 1. In fact, all we need to do is to supersede "edges" by "directed edges"(left as an exercise for the readers).
\(\Box\)
Now we will prove something similar to Theorem 4, but in the spirit of directed graphs as well.
- Theorem 6
Proof First we prove the "\(\Rightarrow\)" part(the trivial one). Indeed, if there's a Hamiltonian cycle, that cycle would provide a directed path from any vertex to any other vertex(by omitting the last edge in a cycle, we have a path). So T is strongly connected.
Then we prove the "\(\Leftarrow\)" part(the non-trivial one).
Claim: T contains a cycle(not necessarily Hamiltonian)
Proof of the claim: Assume T doesn't. Then, for \(xy, yz \in E(T)\), we must have \(xz \in E(T)\) because otherwise there would be a cycle of length 3. So T is transitive, in which the vertices can be listed from left to right such that \(ij \in E(T)\) if and only if j is on the right of i. But such a T isn't strongly connected as no path goes from right to left. Contradiction.
Now let \(C=y_1y_2...y_ky_1\) be a cycle of maximal length in T, and assume \(C\) isn't Hamiltonian. As T is strongly connected and C doesn't contain all of \(V(T)\), there exists an edge from C to some vertex \(x \notin C\). Say this edge is \(y_1x\). Note that if \(xy_2\) were an edge, \(y_1xy_2...y_ky_1\) would be a cycle longer than C, contradicting C's maximality. Therefore, \(y_2x, y_3x,..., y_kx \in E(T)\).
Let \(Z\) be the set of vertices \(z \in V(T)\) such that \(y_1z \in E(T)\). By the observation above, \(\forall z \in Z, i=1,..., k\), we must have \(y_iz \in E(T)\) for the sake of not contradicting C's maximality. Let zt be an edge with (z \in Z\) and \(t \notin Z\)(such an edge exists because of the strong connectivity. More specifically, if there is no such edge, then the outdegree of z would be 0, meaning z can't get to any other vertex(you may think it has a negative divergence), contradicting the strong connectivity). Again, by the same observation, \(t \notin C\).
Conclusively, \(t \notin C, t \notin Z\), which implies that because of strong connectivity, \(ty_1 \in E(T)\)(if \(y_1t\) is instead an edge, t would be in Z).
However, we now have a new cycle: \(zty_1y_2...y_kz\), which is longer than C. Contradiction.
Thus, C is Hamiltonian.
\(\Box\)