--- title: "Euler Trails and Hamilton Cycles" description: "Use connectivity and degree parity to decide Euler trail existence. Apply sufficient conditions for Hamilton cycles and compare what is known about the two decision problems." canonical: https://lightmysky.com/learn/mathematics/euler-trails-and-hamilton-cycles-mt_RU5P5Iqekt source: https://lightmysky.com/learn/mathematics/euler-trails-and-hamilton-cycles-mt_RU5P5Iqekt.md retrieved: 2026-11-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # Euler Trails and Hamilton Cycles Use connectivity and degree parity to decide Euler trail existence. Apply sufficient conditions for Hamilton cycles and compare what is known about the two decision problems. Subject: Mathematics · Area: Discrete Mathematics · Ages 21 to 22 Page: https://lightmysky.com/learn/mathematics/euler-trails-and-hamilton-cycles-mt_RU5P5Iqekt ## Ready when they can - State and prove the degree condition for an Euler circuit and for an Euler trail - Give sufficient conditions for a Hamilton cycle and explain why they are not necessary - Contrast the two problems in terms of how hard each is to decide ## Lesson: Euler trails and Hamilton cycles As with trees, we use vertices, edges and connected components. Here graphs are finite and undirected and have at least one edge. Degree counts incident edge ends; a loop counts twice. Adding all degrees counts each edge twice, so the number of edges is half the degree sum. For a triangle, 2 + 2 + 2 = 6 edge ends give 3 edges. An Euler trail uses every edge once; it may be open or closed. A closed Euler trail is an Euler circuit. A circuit exists exactly when all vertices with edges are in one connected component and every degree is even. Isolated vertices have no edges to cover. For necessity, pair each arrival with a departure. At the start, pair the first departure with the final arrival. Every edge end is paired, so every degree is even. For sufficiency, follow unused edges until you cannot continue. Even degrees prevent stopping away from your start, so the trail closes. Removing its edges leaves even degrees. If edges remain, connectivity gives a vertex on the current trail with unused incident edges. Build another closed trail there and insert it into the route. Repeat. Each insertion uses more edges, so a finite graph eventually has every edge covered. An Euler trail exists exactly when all vertices with edges are in one component and the odd-degree count is zero or two. Zero gives a circuit. Two gives an open trail whose endpoints are the odd vertices. At intermediate visits, arrivals pair with departures. An open route leaves one unpaired departure at its start and one unpaired arrival at its end. To prove existence with two odd vertices, add a temporary edge between them. Allow a parallel edge if they are already adjacent. Both odd degrees become even. The circuit result now applies. Write an Euler circuit with the temporary edge last, then delete that edge. The remaining route uses every original edge once and runs between the original odd vertices. A Hamilton cycle visits every vertex once, then returns to its start. Only the start repeats in its written route. A Hamilton path visits every vertex once without closing back to the start. In a simple graph, a Hamilton cycle has at least three vertices. It uses n edges on n vertices and can skip other edges. Euler circuits cover every edge but may repeat vertices. For the following degree rules, the graph is simple and undirected, with n >= 3 vertices. Simple means no loops or parallel edges. Dirac's theorem guarantees a Hamilton cycle if every degree is at least n/2. Ore's theorem guarantees one if deg(u) + deg(v) >= n for every pair of distinct nonadjacent vertices u and v. These conditions are sufficient: meeting either bound guarantees a cycle. **Example.** Dirac's bound is sufficient: for a simple undirected graph with n >= 3, every degree at least n/2 guarantees a Hamilton cycle. The cycle graph on seven vertices has one around its ring, yet every degree is 2, below 7/2. Nonadjacent vertices have degree sum 4, below Ore's bound 7. Thus neither condition is necessary. Failing either bound alone does not decide whether a Hamilton cycle exists. A necessary condition differs from a sufficient condition. Every vertex on a Hamilton cycle needs two distinct incident edges, one to enter and one to leave. Degree 0 or 1 rules out a Hamilton cycle. Adjacency lists record incident edge ends at each vertex; a loop appears twice. Start at a vertex with edges and mark it. Repeatedly scan a reached vertex's list once, marking unseen neighbors to explore next. Check all vertices with edges were reached, and count list entries for degrees. With adjacency lists, scan V vertices and 2E listed edge ends, where V counts vertices and E counts edges. Marking each vertex and scanning each list once checks connectivity and degrees in O(V + E) time. This decides Euler trail existence. Hamilton cycle existence on general simple undirected graphs is NP-complete. No polynomial-time algorithm is known, but none has been proved impossible: whether P = NP is open. A proposed Hamilton cycle can be checked in polynomial time. To check an Euler circuit, list its consecutive undirected edges. Check each is present, none repeats, every graph edge is used, and the route closes. A closed route that omits an edge is not Euler. For a Hamilton cycle in a simple undirected graph, require at least three vertices. Check every graph vertex occurs exactly once before the repeated start, the route closes, and every consecutive edge is present with no edge repeated, including the closing edge. **Recap.** Check connectivity and odd degrees for Euler trails. Hamilton degree bounds give guarantees, not a complete test. No polynomial-time general Hamilton algorithm is known. *Original lesson, questions and flashcards written for this learning dataset.* ## Practice 14 questions on this page, each with its working shown. ## Needs first - [Trees and Spanning Trees](https://lightmysky.com/learn/mathematics/trees-and-spanning-trees-mt_kMWpsz44yJ) ## Optional connections - [P, NP and What NP-Complete Means](https://lightmysky.com/learn/computing/p-np-and-what-np-complete-means-mt_wwmNVG_VnB) ## Opens up - [Graph Colouring and Planarity](https://lightmysky.com/learn/mathematics/graph-colouring-and-planarity-mt_6xy6UPBppw)