While writing the Eulerian path wiki, I had an instructive blind spot in one of the proofs I was writing up.
To understand this note, you'll want to read the wiki, or at least know what a graph is (a collection of vertices and edges) and what the degree of a vertex is (the number of edges that emanate from the vertex).
An Eulerian path is a trip around the graph that passes through each edge exactly once, and an Eulerian circuit is an Eulerian path that starts and ends in the same place.
The two main theorems in the wiki are
(1) For a finite, connected graph, an Eulerian circuit exists if and only if every vertex has even degree
(2) For a finite, connected graph, an Eulerian path exists if and only if or vertices have odd degree.
The proof of (1) is in the wiki (it involves inductively constructing the circuit via an explicit algorithm). The blind spot I had was: how does (1) imply (2)? That is, if I have two vertices of odd degree, how can I construct an Eulerian path, given the information that Eulerian cycles exist on graphs where every vertex is even?
If there are two vertices of odd degree, it's clear that the Eulerian path will have to start at one of them and end at the other one. So my first idea was to start by walking along the graph from one of them to the other (using the fact that the graph is connected), and then to use (1) to make a circuit on the graph that remains after deleting the edges I already used. It's clear that this graph will have every vertex of even degree.
The problem with this idea is the graph may no longer be connected, so there is not necessarily a circuit. (Imagine, for instance, if the two odd-degree vertices had degree 1, and the graph looked like the Greek letter . Starting by walking from the top of the to the bottom will not lead to an Eulerian path on that graph.)
I had a vague idea that there might be a way to get around this issue, but while I was thinking about it I happened to read the very short and elegant argument that proves that (1) implies (2). It is the kind of thing that is extremely obvious once you see it, but is easy to miss if you haven't seen it. Can anyone see what that argument is?
Easy Math Editor
This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.
When posting on Brilliant:
*italics*
or_italics_
**bold**
or__bold__
paragraph 1
paragraph 2
[example link](https://brilliant.org)
> This is a quote
\(
...\)
or\[
...\]
to ensure proper formatting.2 \times 3
2^{34}
a_{i-1}
\frac{2}{3}
\sqrt{2}
\sum_{i=1}^3
\sin \theta
\boxed{123}
Comments
Generalize the statement to apply to multigraphs (you allow multiple edges between the same pair of vertices). Add an edge between the two odd vertices. Get the Eulerian circuit. Remove the new edge; you now have an Eulerian path.
Log in to reply
Right. The idea of temporarily adding an edge is very pretty, and it definitely did not occur to me since I was concentrating on deleting edges instead.
@Ivan Koswara