Graph theory blind spot

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 0 0 or 2 2 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 ϕ \phi . Starting by walking from the top of the ϕ \phi 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?

Note by Patrick Corn
5 years, 3 months ago

No vote yet
1 vote

  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:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list
  • bulleted
  • list

1. numbered
2. list
  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai−1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 ∑i=13 \sum_{i=1}^3
\sin \theta sin⁡θ \sin \theta
\boxed{123} 123 \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.

Ivan Koswara - 5 years, 3 months ago

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.

Patrick Corn - 5 years, 3 months ago

@Ivan Koswara

Nihar Mahajan - 5 years, 3 months ago
×

Problem Loading...

Note Loading...

Set Loading...