Eulerian circuit
…or there and back again
Beware reader! Stuff described here requires some background and could be pretty tricky. You won’t get discouraged, will you? Google what you don’t understand, find additional resources and you will nail this knowledge.
¡No pasarán!
Seven bridges of Königsberg (famous birthplace of Immanuel Kant; now Kaliningrad) was an old topological puzzle riddling this: is it possible to cross all the seven bridges in the city (depicted on the image above) without crossing any bridge twice? Solution, devised by Euler in 1736, led to the invention of what we call today “Graph Theory” and, specifically, to the notion of Eulerian Circuit, that we are discussing in this article.
Abbreviations
EC: Eulerian Circuit
G: some graph G
V: set of all the vertices in G
E: set of all the edges in G
Some definitions recap
Walk (or X -> Y walk) — sequence of alternating vertices and edges from vertex X to Y.
Trail — such a walk in which all the edges are distinct.
Path — such walk in which all the vertices and edges in the sequence are distinct.
Circuit (or a closed trail) — such a trail in which the first and final vertices are equal.
Degree of a vertex — number of edges incident to some vertex V. Denoted as deg(V). Keep in mind, that a loop on a vertex contributes +2 degrees.
Connected graph — if for all V₁, V₂ in the set of vertices (V) of a graph G there exists a path from V₁ to V₂, then G is connected.
What is an Eulerian Circuit?
A graph G is said to have Eulerian Circuit if it is possible to construct such a circuit that traverses every edge in E.
How to tell if some graph G has an EC?
It’s pretty straightforward. Graph G is said to have an EC if and only if the following properties hold:
1. it is connected
2. for all Vᵢ in V deg(Vᵢ) is even
Quite easy, isn’t it, huh? We’ve learned what an Eulerian Circuit is and what properties it has. But are you willing to just take my word for it? I sure hope not. Neither do i would be satisfied with just a definition.
You’ve guessed it! It’s time to do some…
Proofs
What are trying to prove? That if in some connected graph G all of its vertices have an even number of degrees, then it has EC.
Edges number induction:
Theorem:
Let V be the set of vertices and E set of edges of graph G.
Statement A: for all Vᵢ, Vⱼ there exists a path from Vᵢ to Vⱼ.
Statement B: for all Vᵢ, deg(Vᵢ) = 2k, where k ∈ ℤ+.
Statement C: G contains EC.
A ∧ B <=> C
Get Roman’s stories in your inbox
Join Medium for free to get updates from this writer.
Induction hypothesis:
For |E| = n, assume that A ∧ B <=> C.
Base cases:
1) |E| = 1. The only way to construct a graph with one edge and even number of degrees on every vertex is to loop the single vertex on itself(Image 2).
2) |E| = 2. Since there are just two edges and deg(Vᵢ) is even the edges have to be between two vertices (Image 2).
Induction step:
Given T(n) is true, show that T(n+1) is true:
1. Let G be a graph connected graph with deg(Vᵢ) being even, where |E| = n+1.
2. Lemma 1.1: For a connected graph with |V| ≥ 2, ∃ Vᵢ such that the set of vertices formed by V-Vᵢ and set of edges formed by removing all the edges incident to Vᵢ still forms a connected graph. In other words, for a connected graph with two or more vertices, there exists such a vertex that can be removed with its incident edges with disconnecting the graph.
The proof for lemma 1.1 is written below. Surprisingly (or not?), that proof will be the hardest part of this article.
Pick vertex Vₓ, such that its removal does not lead to graph disconnection. According to lemma 1.1, the graph will still be connected after removal of Vₓ and its incident edges.
3. By point 1, Vₓ has at least two edges.
4. Pick two edges incident to Vₓ. Say, (x, Vₓ) and (Vₓ, y). Remove them, then add (x, y) back to form G₁.
5. G₁ is connected, since we removed such a vertex that doesn’t disconnect G.
6. G₁ has n edges, since we remove 2 from n+1 and added 1 back.
7. By inductive hypothesis G₁ contains EC. Name it C.
8. Add (x, Vₓ) and (Vₓ, y) back.
9. Traverse C within G.
10. Instead of walking through (x, y), walk through (x, Vₓ) and then (Vₓ, y).
11. Since x and y are connected to the EC in G₁, we have an EC in G.
QED.
Proof of Lemma 1.1 (induction on number of vertices)
Theorem:
For every connected graph with two or more vertices there exists a vertex after removal of which, with its incident edges, graph remains connected.
Strong Induction hypothesis:
In a connected graph with n vertices there exist two vertices Vₓ and Vᵧ, that can be removed, any one of them, with their incident edges without disconnecting the graph. Where Vₓ ≠ Vᵧ.
Base case:
|V| = 2. Either V₁ or V₂ can be removed, since single vertex is considered a connected graph.
Induction step:
Given T(2) ∧ …T(k) ∧ T(n) are true, where 2 ≤ k ≤ n, show that T(n+1) is true:
For simplicity and better visualization we will keep near a concrete example, where n = 5. This contradicts to the abstract manner of induction proof, but it will help us better understand this fairly convoluted theorem.
- Remove random vertex Vᵩ from G to get G₁.
Case 1: G₁ is still connected:
1) Suppose, we removed vertex Q. By our hypothesis in G₁ (since |V|= n) there exist two vertices A and Vᵢ (say, T) that can be removed without disconnecting it. It’s crystal clear (especially with the illustrated graph above) that if we removed A from G resulting graph would still be connected. So there is at least two vertices that can be removed from G without disconnecting it. Therefore, we are done.
Case 2: G₁ has been disconnected:
1) G₁ contains at least 2 distinct components. This follows out of the assumption made in the inductive step. Because |V| = n+1 in G and n ≥ 2 after removing the vertex that disconnects G at least 2 vertices remain. And since G₁ is disconnected they have to be in separate components.
To visualize this, suppose, F was removed.
2) Case 2.1: Each component contains a vertex Vₓ that is the only vertex in it.
Suppose the graph illustrated in Image 6 was the initial graph G. Then suppose we removed Y.
{T} and {L} are both graph contained of an isolated vertices. And a graph with one vertex is still a graph, that has |V| = 1. And his sole vertex’s deg is just 0.
Draw vertex Y back. Remove T. G₁ is connected. Or. Draw vertex Y back. Remove L. G₁ is connected. Both T and L can be removed from G without disconnecting it. Therefore, we are done.
3) Case 2.2: at least one of the components (Cₓ) has |V| ≥ 2. Just for a better visualization we can use Image 4 to be the initial graph G and Image 5 to be G₁. Once again, keep in mind: only the comprehension in abstract terms will provide you a strong knowledge.
- We assumed that T(n) is true and that n ≥ 2 and by the statement of case 2.2 Cₓ has |V| ≥ 2, so, by induction hypothesis in component Cₓ there exist two vertices that can be removed without disconnecting it.
- Lets say the vertices that can be removed safely from Cₓ are Vₓ and Vᵧ, where Vₓ ≠ Vᵧ. At least one of them, say Vₓ, is not equal to the originally removed vertex. Vₓ ≠ Vᵩ. So, Vₓ is safe to remove from G. This follows from the fact, that disconnecting a component of G is also disconnecting G itself. So, if it’s safe to remove from Cₓ then it’s also safe for G.
- We also know that there is at least one other component Cᵧ.
- If in Cᵧ |V| = 1, we can safely remove it. This one in pair with Vₓ sum up to two distinct vertices that can be removed. Therefore, we are done.
- If in Cᵧ |V| > 1 same rules as in p.1 and p.2 apply. That means in Cᵧ we can find a vertex that doesn’t equal to Vᵩ and combine it with Vₓ and get two distinct vertices that can be removed. Therefore, we are done.
QED.
