maths.free › Combinatorics & Graph Theory › 5. Graph Theory › Eulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs

Graph theory is an area of mathematics that has found many applications in a variety of disciplines. Throughout this text, we will encounter a number of them.

Eulerian and Hamiltonian Graphs

Graph theory is an area of mathematics that has found many applications in a variety of disciplines. Throughout this text, we will encounter a number of them. However, graph theory traces its origins to a problem in Königsberg, Prussia (now Kaliningrad, Russia) nearly three centuries ago. The river Pregel passes through the city, and there are two large islands in the middle of the channel. These islands were connected to the mainland by seven bridges as indicated in . It is said that the citizens of Königsberg often wondered if it was possible for one to leave his home, walk through the city in such a way that he crossed each bridge precisely one time, and end up at home again. Leonhard Euler settled this problem in 1736 by using graph theory in the form of .

Let \(\bfG\) be a graph without isolated vertices. We say that \(\bfG\) is eulerian provided that there is a sequence \((x_0,x_1,x_2,\dots,x_t)\) of vertices from \(\bfG\), with repetition allowed, so that

  1. \(x_0=x_t\)
  2. \(i=0,1,\dots, t-1\)\(x_ix_{i+1}\)\(\bfG\)
  3. \(e\in E\)\(i\)\(0\le i\lt t\)\(e=x_ix_{i+1}\)

When \(\bfG\) is eulerian, a sequence satisfying these three conditions is called an eulerian circuit. A sequence of vertices \((x_0,x_1,\dots,x_t)\) is called a circuit when it satisfies only the first two of these conditions. Note that a sequence consisting of a single vertex is a circuit. Before proceeding to Euler's elegant characterization of eulerian graphs, let's use SageMath to generate some graphs that are and are not eulerian.

Run the code below. It will execute until it finds a graph \(\bfG\) that is eulerian. The output that will be produced is a list of the degrees of the vertices of the graph \(\bfG\) followed by a drawing of \(\bfG\).

We encourage you to evaluate the run the code above multiple times, even changing the number of vertices and edges. If it seems to be running a log time, it may be that you have made the number of edges too small, so try increasing it a bit. Do you notice anything about the degrees of the vertices in the graphs produced?

Now let's try to find a graph \(\bfH\) that is not eulerian. Again, the output is the list of degrees of \(\bfH\) followed by a drawing of \(\bfH\).

One thing you probably noticed in running this second block of code is that it tended to come back much faster than the first. That would suggest that the non-eulerian graphs outnumber the eulerian graphs. Did you notice anything different about the degrees of the vertices in these graphs compared to the ones that were eulerian?

The following elementary theorem completely characterizes eulerian graphs. Its proof gives an algorithm that is easily implemented.

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.

Practice (3)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

  1. Write a couple of sentences to explain informally the difference between a graph being eulerian and a graph being hamiltonian. If possible, give an example (other than the rather silly bridge problem in the text) where each concept would be useful.

  2. Briefly but specifically explain why the graph \(\bfH\) in is not eulerian.

  3. Try your hand at finding the eulerian circuit in \(\bfG\) in by following the method illustrated in the text. Instead of giving all the steps or the final circuit here, just give the circuit that you come up with after the initial trivial circuit \((1)\).

Symbols used here

x \in A,\ A \subseteq B
element of, subset
x belongs to A; every element of A is in B.
i
imaginary unit
i² = −1.
\leq,\ \geq
less/greater than or equal
Inequalities that allow equality; < and > exclude it.
n!
factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
\binom{n}{k}
binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).
\sum_{k=1}^{n} a_k
summation
Add a_k for k = 1 up to n.
\prod_{k=1}^{n} a_k
product
Multiply a_k for k = 1 up to n.
\emptyset,\ |A|
empty set, cardinality
The set with no elements; the number of elements of A.

Questions people ask

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

Опитай си.

Parts of this page are adapted from Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

Още в Combinatorics & Graph Theory

The counting principlesPigeonhole principle and inclusion–exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs