Separate using every edge from visiting every vertex
Apply Euler parity conditions and recognize the limits of Hamiltonian heuristics.
Loading your saved responses…
Try
Walking every road once is an edge problem; visiting every town once is a vertex problem. An Euler trail uses every edge exactly once. A Hamilton cycle visits every vertex exactly once and returns to its start, without requiring every edge to be used.
Predict
Predict what a trail’s interior vertices require. Every arrival must pair with a departure. An Euler circuit therefore requires all degrees even. An open Euler trail has exactly two odd-degree endpoints. Connectivity is required among vertices incident to edges; isolated vertices do not obstruct an edge traversal.
Experiment
Draw two triangles sharing one vertex. Trace an Euler circuit through both triangles. Try to make a Hamilton cycle and identify why moving between the triangles would force revisiting the shared vertex. The same graph answers the two questions differently.
Two triangles share vertex S. An Euler circuit is S–A–B–S–C–D–S. No Hamilton cycle can pass between the triangles without revisiting the cut vertex S. The layout is schematic.
Understand
Worked Euler existence argument: in a finite undirected graph whose nonisolated part is connected and all degrees are even, start following unused edges until returning to the start. Even degrees prevent getting stuck elsewhere. If unused edges remain, connectivity supplies a vertex on the current tour with access to unused edges; build another closed tour there and splice it in. Finitely many edges make the process finish. With exactly two odd vertices, add an auxiliary edge between them, find a circuit in the resulting multigraph, then remove that edge to obtain an open trail.
Hamiltonian existence has no analogous all-purpose degree-parity criterion. The shared vertex in the two-triangle graph is a cut vertex, obstructing a Hamilton cycle.
Invalid inference: every connected even-degree graph has a Hamilton cycle. The example refutes it.
Apply
State whether your object is an edge sequence or vertex cycle and verify exactly what is used once. For Euler conditions, check connectivity as well as parity. Degree-one vertices rule out a Hamilton cycle in a graph with at least three vertices.
Continue
Depth: sufficient Hamiltonian degree conditions and algorithmic complexity belong to further graph theory. Failure of one sufficient condition does not prove impossibility. Finding a valid explicit cycle is a certificate; failing to find one in a limited search is not.
Apply · explain · revise
Practice and reasoning
Drafts save locally as you type. Reveal worked solutions when useful; the site remembers that exposure. Automatic matches check the requested answer, while written arguments require review against the rubric.
How many odd-degree vertices must an undirected graph with an open Euler trail (distinct endpoints) have?
Integers, fractions and finite decimals are accepted. Expressions such as sqrt(2) are not parsed by this checker.
In the cycle graph C₇, what is each vertex's degree?
Integers, fractions and finite decimals are accepted. Expressions such as sqrt(2) are not parsed by this checker.
A Hamilton cycle must:
For star K₁,₄, which claim is correct?
Prove that every vertex has even degree in a graph with an Euler circuit.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Give a connected simple graph with an Euler circuit but no Hamilton cycle, and justify both claims.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Reflect and continue
Before marking this lesson complete, explain one key idea without the worked solution and identify a condition that matters. Marking complete records participation, not independent mastery.
