Euler and Hamilton Ideas in Graph Theory II

students, imagine planning a route through a city 🗺️. You might want to visit every street exactly once, or every landmark exactly once, while ending in a useful place. Graph theory turns these questions into mathematical problems about vertices and edges. In this lesson, you will learn the main ideas behind Euler and Hamilton concepts, how to recognize them, and how they connect to other parts of Graph Theory II.

By the end of this lesson, you should be able to:

explain the meaning of Eulerian and Hamiltonian ideas,
use rules and examples to decide whether a graph has certain paths or cycles,
connect these ideas to connectivity and bipartite graphs,
summarize why these topics matter in graph theory,
apply reasoning to solve simple route and network problems. ✅

Euler ideas: using every edge

The Euler idea is about edges. A graph is called Eulerian if it has a closed walk that uses every edge exactly once. This special closed walk is called an Euler circuit. If a graph has a trail that uses every edge exactly once but does not have to end where it started, that trail is called an Euler trail.

A few terms matter here:

A walk is a sequence of vertices connected by edges, and vertices or edges may repeat.
A trail is a walk with no repeated edges.
A circuit is a closed trail, meaning it starts and ends at the same vertex.

The most famous historical example is the problem of the seven bridges of Königsberg. People asked whether one could walk across each bridge exactly once. Leonhard Euler showed that this was impossible, and that problem helped create graph theory. That is why Euler ideas are so important in Discrete Mathematics. 🌉

The key rule for Euler circuits

For a connected graph to have an Euler circuit, every vertex must have even degree. The degree of a vertex is the number of edges touching it.

Why does even degree matter? Each time you enter a vertex along one edge, you must leave along another edge. That pairing of entrance and exit edges requires an even number of edges at every vertex. The starting vertex also needs to match this rule because the walk ends where it began.

So the rule is:

a connected graph has an Euler circuit if and only if every vertex has even degree.

Example: consider a square made of 4 vertices and 4 edges, like a cycle. Each vertex has degree $2$, so all degrees are even. Therefore, the graph has an Euler circuit. You can start at any vertex, go around the square, and return to the start while using each edge once.

The rule for Euler trails

A connected graph has an Euler trail if and only if exactly $0$ or $2$ vertices have odd degree.

If there are $0$ odd-degree vertices, the graph has an Euler circuit, which is also an Euler trail.
If there are exactly $2$ odd-degree vertices, the trail must start at one odd vertex and end at the other.

Example: suppose a graph has vertices with degrees $3, 3, 2, 2$. There are exactly $2 odd-degree vertices, so an Euler trail exists. The trail begins at one odd-degree vertex and ends at the other. This is useful in planning routes like snowplowing streets or mail delivery, where you want to reduce repeated travel 🚚.

How to test a graph for Euler ideas

To decide whether a graph has an Euler circuit or trail, follow these steps:

Check that the graph is connected, ignoring isolated vertices if needed.
Count the degree of every vertex.
Count how many vertices have odd degree.
Apply the rule:

$0$ odd-degree vertices means Euler circuit.
$2$ odd-degree vertices means Euler trail but not a circuit.
more than $2$ odd-degree vertices means neither.

This procedure is a clear example of mathematical reasoning: you do not guess, you use structure and degree counts.

Hamilton ideas: visiting every vertex

Hamilton ideas are different. Instead of focusing on edges, they focus on vertices. A graph is Hamiltonian if it contains a cycle that visits every vertex exactly once. This is called a Hamilton cycle. If a graph has a path that visits every vertex exactly once but does not return to the starting point, that is a Hamilton path.

Unlike Euler problems, Hamilton problems do not have a simple complete test like the degree rule for Euler circuits. That makes Hamilton questions more challenging and more famous in graph theory. Often, you must use examples, patterns, or theorems to decide whether a graph is Hamiltonian.

Hamilton path versus Hamilton cycle

A Hamilton path uses every vertex exactly once. A Hamilton cycle does the same but also returns to the start.

Example: imagine a tour of five cities where you want to visit each city once. If you can start in one city, travel through the others, and stop at the last city without returning, that is a Hamilton path. If you can return to the first city and still avoid repeats, that is a Hamilton cycle. ✈️

A simple cycle graph, such as a pentagon, is Hamiltonian because you can go around the cycle and visit each vertex exactly once before returning to the start.

Important differences from Euler ideas

It helps to compare the two ideas:

Euler concerns edges.
Hamilton concerns vertices.
Euler problems often ask: “Can I use every road exactly once?”
Hamilton problems often ask: “Can I visit every place exactly once?”

This difference can change the answer dramatically. A graph may have an Euler circuit but no Hamilton cycle, or a Hamilton cycle but no Euler circuit.

For example, a graph could have all even degrees and still fail to have a Hamilton cycle because its structure may not allow a single loop through every vertex. On the other hand, a cycle graph has a Hamilton cycle, but if every vertex has degree $2$, it may also satisfy Euler rules. In many real graphs, though, the two properties do not come together.

Examples and reasoning with real graph structures

Let’s use a few graph patterns to build intuition.

Example 1: a simple cycle

Take a triangle or square. Every vertex has degree $2$.

Euler: all degrees are even, so an Euler circuit exists.
Hamilton: the cycle itself visits every vertex exactly once, so a Hamilton cycle exists.

This is the cleanest case where both ideas appear together.

Example 2: a star graph

A star graph has one central vertex connected to several outer vertices. The outer vertices each have degree $1$, which is odd.

Euler: there are many odd-degree vertices, so there is no Euler trail or circuit.
Hamilton: the graph also has no Hamilton cycle because the center would have to be visited more than once to reach all leaves.

This shows that high branching can make both ideas fail.

Example 3: a graph shaped like two triangles sharing one vertex

In this graph, some vertices may have even degree while others may have odd degree. If exactly $2$ vertices are odd, an Euler trail exists. But a Hamilton cycle may still fail because the shared vertex creates a bottleneck. A Hamilton cycle would need to pass through every vertex exactly once, but a bottleneck can make that impossible.

This example shows why Hamilton questions often require more than degree counting.

Connections to connectivity and bipartite graphs

Euler and Hamilton ideas fit into the bigger picture of Graph Theory II because they depend on how a graph is connected and how its vertices are arranged.

Connectivity matters

A graph must be connected for an Euler trail or circuit to exist, except for isolated vertices that do not affect the route. If a graph has two separated components, there is no way to travel through all edges in one continuous walk.

For Hamilton paths and cycles, connectivity is also necessary, but not enough. A graph can be connected and still have no Hamilton cycle. So connectivity is a starting point, not a guarantee.

Bipartite graphs and Hamilton ideas

A bipartite graph has its vertices split into two sets, and every edge goes between the two sets. Bipartite structure strongly affects Hamilton cycles.

In a bipartite graph, any cycle must alternate between the two parts. That means every cycle has even length. So if a bipartite graph has a Hamilton cycle, the number of vertices must be even, because the cycle must alternate and include all vertices exactly once.

This gives a useful test:

if a bipartite graph has an odd number of vertices, it cannot have a Hamilton cycle.

However, a bipartite graph may still have a Hamilton path, depending on its structure.

Why these ideas matter in applications

These concepts appear in route planning, computer networks, puzzle design, and scheduling. Euler ideas model situations where every connection must be used, like street cleaning or circuit tracing. Hamilton ideas model situations where every location must be visited once, like delivery planning or ordering tasks. Both ideas help turn a real-world problem into a graph problem that can be studied logically. 📘

Conclusion

Euler and Hamilton ideas are central topics in Graph Theory II because they show two different ways to study routes in graphs. Euler problems ask about using every edge exactly once, while Hamilton problems ask about visiting every vertex exactly once. Euler graphs have a clear degree rule, which makes them easier to test. Hamilton graphs are harder to characterize and often require deeper reasoning.

students, when you study these ideas, focus on the difference between edges and vertices, and remember that connectivity, degree, and graph structure all matter. These ideas connect directly to broader graph theory topics and show how mathematics can model movement, networks, and efficient routes. ✅

Study Notes

An Euler trail uses every edge exactly once.
An Euler circuit is an Euler trail that starts and ends at the same vertex.
A connected graph has an Euler circuit if and only if every vertex has even degree.
A connected graph has an Euler trail if and only if exactly $0$ or $2$ vertices have odd degree.
A Hamilton path visits every vertex exactly once.
A Hamilton cycle visits every vertex exactly once and returns to the start.
Euler ideas are about edges; Hamilton ideas are about vertices.
Connectivity is necessary for both ideas, but not sufficient for Hamilton cycles.
In a bipartite graph, every cycle has even length.
A bipartite graph with an odd number of vertices cannot have a Hamilton cycle.
Real-world uses include route planning, delivery systems, and network design. 🌟