Check what may repeat before deciding whether a route satisfies a task.
By the end: classify a route and distinguish visiting all vertices from using all edges.
A walk is a sequence of vertices whose consecutive pairs are joined by permitted edges. Vertices and edges may repeat. A trail is a walk that never repeats an edge. In this course, a path never repeats a vertex. A cycle returns to its starting vertex and otherwise has distinct vertices and edges. An undirected cycle therefore needs at least three edges in a simple graph.
Terminology varies. Some references use path for a walk or a trail and say simple path when they forbid repeated vertices. Check the definition rather than relying on the word. We count length as the number of traversed edges; cost is the sum of their weights. A zero-edge path from a vertex to itself is allowed, but is not a cycle.
A proposed route makes two different claims. It claims that each step is permitted, and it claims to obey a repetition rule. Check permission first. In the fixed network the vertices are A, B, C, D, E, F, and the undirected edges are AB, AC, BC, BD, CE, DE, EF. These seven pairs are the complete record. The sequence A, C, E, D is valid because AC, CE, and ED all occur in that record, with ED naming the same undirected edge as DE. Its length is three, although it names four vertices.
Now consider A, C, D, E. Every named vertex exists, but the step from C to D does not. Neither the visible closeness of C and D nor the existence of a longer connection grants that missing step. Replacing C, D with C, B, D would repair the sequence, but it would describe a different walk with an additional step. This distinction matters when inspecting an itinerary. A list of legitimate destinations is not necessarily a legitimate route. The relation between each consecutive pair must also be present in the graph.
| Sequence | Required edges | Permission |
|---|---|---|
| A, C, E, D | AC, CE, DE | All present |
| A, C, D, E | AC, CD, DE | CD absent |
| A, C, B, D, E | AC, BC, BD, DE | All present; four steps |
To test edge repetition, write one edge name below each consecutive pair. For A, B, C, A, C, the edge list is AB, BC, AC, AC. The final step reuses AC in the opposite direction. Reversing an undirected edge does not make it new. The route therefore fails the trail rule, even though its first three steps form a cycle. Counting distinct highlighted edges would give three, while counting traversals gives four. A picture that thickens each used edge once cannot preserve this difference without a separate sequence or count.
Vertex repetition asks a stricter question. In the same fixed graph, A, B, C, A, B repeats A and B, but it also repeats AB, so it fails both tests. A more informative contrast is A, B, C, A, with edge list AB, BC, AC. Every edge is different, yet A appears twice. It is a trail and a cycle, but not a path under this course's definition. Categories overlap in specific ways. Every path is a trail in these simple graphs, but a trail need not be a path.
A route that names only C has no steps to check. It is a valid zero-edge path from C to itself. It also repeats no edge, but it is not a cycle because it makes no nonempty return journey. By contrast C, E, C makes two traversals of one undirected edge. It is closed, meaning it ends where it starts, but it is not a cycle here. Closure alone says nothing about whether an edge or an intermediate vertex repeats. This is why the word closed cannot replace the separate repetition tests.
| Walk | Edges in traversal order | Distinct / traversed |
|---|---|---|
| A, B, C, A | AB, BC, AC | 3 / 3 |
| A, B, C, A, C | AB, BC, AC, AC | 3 / 4 |
| C | None | 0 / 0 |
| C, E, C | CE, CE | 1 / 2 |
Direction changes the permission check and the edge identity check together. Take a separate graph with vertices A, B, C and exactly the directed edges A to B, B to A, and B to C. The sequence A, B, A uses two distinct edges and forms a directed cycle. The sequence C, B, A is invalid because C has no outgoing edge. Neither conclusion depends on where the vertices appear on the page. When comparing references, translate their definitions into these checks. A reference's Eulerian path may mean what this course calls an Euler trail.
In an undirected graph, A to B to A is a valid walk but repeats the same edge. It is not a trail or a cycle under our definitions. In a directed graph with separate A-to-B and B-to-A edges, that sequence uses two different edges and can be a directed cycle. Direction changes the identity of an edge.
An Euler trail uses every edge exactly once. In a finite undirected graph with at least one edge and all non-isolated vertices connected, one exists exactly when there are zero or two odd-degree vertices. With two, they must be the endpoints. At an intermediate visit, each arrival pairs with a departure, explaining the parity requirement. With zero odd vertices, an Euler circuit returns to its start.
Imagine tracing every undirected edge once while keeping a record of unused edges. Whenever you arrive at an intermediate vertex, you must leave along a different unused edge. That visit consumes two incident edges. Revisiting the vertex consumes another pair. Thus every vertex other than the two ends of an open trail needs an even degree. At the start, one departure has no preceding arrival. At the finish, one arrival has no following departure. Those two exceptions account for two odd degrees, even if the trail visits either endpoint again along the way.
Apply this accounting to the fixed seven-edge network. Its degrees in alphabetical order are 2, 3, 3, 2, 3, 1. The odd vertices are B, C, E, F. There are four, so two endpoints cannot absorb all the unmatched incidences. No Euler trail exists, regardless of starting vertex or clever route selection. This is an impossibility result, not a failure to find a route. The obstruction remains even though all six vertices are reachable from one another. Connectivity and degree parity supply different parts of the existence test.
| Vertex | Degree | Unpaired incidence after pairing |
|---|---|---|
| A | 2 | 0 |
| B | 3 | 1 |
| C | 3 | 1 |
| D | 2 | 0 |
| E | 3 | 1 |
| F | 1 | 1 |
A small paper change shows what the obstruction measures. Remove BC while retaining every vertex and every other base edge. B and C each lose one incidence, so their degrees become two. E and F remain odd. The remaining graph is connected and has six edges. An Euler trail is E, C, A, B, D, E, F. Reading its consecutive pairs gives CE, AC, AB, BD, DE, EF, each exactly once. E appears twice before the route finishes at F. That repetition is necessary for this particular edge-covering route and is allowed by the trail rule.
Why are even degrees sufficient when the non-isolated part is connected? Start at a vertex with an unused edge and keep taking unused edges. In an all-even graph, you cannot become stuck at a different vertex. Each arrival there leaves an odd number of unused incident edges, so at least one departure remains. Eventually you return to the start. If some edges remain unused, take a path from the current trail toward an unused edge. The first unused edge on that path touches a vertex already on the trail. Begin another closed trail there and insert it into the first.
The insertion is concrete in a five-vertex graph with edges AB, BC, CA, AD, DE, EA. One closed trail is A, B, C, A, and another is A, D, E, A. Join them at their shared A to obtain A, B, C, A, D, E, A. No edge repeats, although A appears three times. Continuing this insertion process uses all edges because each insertion consumes at least one previously unused edge and the graph is finite. With two odd vertices, start at one and the first trail must stop at the other. Insert any remaining closed trails at shared vertices in the same way.
| Part | Vertex sequence | Edges consumed |
|---|---|---|
| First closed trail | A, B, C, A | AB, BC, AC |
| Insert at A | A, D, E, A | AD, DE, AE |
| Combined | A, B, C, A, D, E, A | All six; no repeats |
Parity alone cannot replace connectivity. Take six vertices A through F with exactly the edges AB, BC, CA, DE, EF, FD. Every degree is two, yet the two triangles have no connection. No continuous walk can cover both sets of edges. An isolated vertex is different because it has no edge that an Euler trail must cover. A triangle plus an isolated fourth vertex therefore has an Euler circuit over all its edges, although the whole graph is disconnected. State the non-isolated connectivity condition rather than silently assuming that every named vertex has an incident edge.
Valid walk of 4 edges.
| Test | Result |
|---|---|
| No repeated edges: trail | Yes |
| No repeated vertices: path | Yes |
| Simple closed route: cycle | No |
| Sequence | A → B → D → E → F |
| Sequence in the displayed graph | Classification |
|---|---|
| A, B, D, E, F | Path of four edges |
| A, B, C, A | Cycle and trail, not a path |
| A, B, A, C | Walk with a repeated edge |
| A, F | Invalid: no such edge |
The walk model keeps one graph and changes only its proposed sequence. Begin with A-B-D-E-F. The successive edges are AB, BD, DE, EF. None repeats, and all five named vertices differ, so the result is a path of length four. C remains in the graph even though this route does not visit it. The path label therefore does not promise to visit every vertex. Nor does the visible unused AC edge invalidate the route. Ordinary path classification concerns the submitted sequence, not coverage of the available graph.
Compare that selection with A-B-C-A. Its three steps use the triangle near A, while D, E, and F are unused. The cycle report says that the sequence returns to its start without other repetition. It does not claim that the whole graph is a cycle or that the route uses every edge. In fact, the graph also contains the cycle B, C, E, D, B, using BC, CE, DE, BD. A graph may contain several cycles even when one selected sequence highlights only one of them. The selected route and its surrounding graph are different objects.
| Proposal | Length if valid | Reason for report |
|---|---|---|
| A, B, D, E, F | 4 | Path and trail; C unvisited |
| A, B, C, A | 3 | Cycle and trail; A repeated |
| A, B, A, C | 3 | Walk only; AB repeated |
| A, F | Invalid | No AF edge |
Next select A-B-A-C. The model highlights AB and AC, but the written sequence has three steps, not two. AB occurs twice and AC once. Both the path and trail reports are false because A repeats and AB repeats. The sequence is nevertheless a valid walk. If someone copied only the highlighted edge set into a report, the evidence would no longer establish those repeated traversals. The sequence provides the missing order and multiplicity. This is a limitation of set highlighting, not a disagreement between the graph picture and the classifier.
Finally select A-F. This proposal has two distinct vertex names and no repeated edge name, but there is no AF edge. The permission test fails before either repetition rule can make it a path or trail. A valid replacement is A, C, E, F, with three steps. Another is A, B, D, E, F, with four. Both establish reachability from A to F, but the shorter candidate supplies stronger evidence about edge count. Merely seeing that all letters exist would miss the reason the original proposal fails.
You can simplify a repeated walk without changing its endpoints. In the paper sequence A, B, C, A, C, E, F, the first return to A encloses the closed part A, B, C, A. Delete that part while keeping its shared endpoint once. The result is A, C, E, F. It remains valid because the edge leaving the second A can now leave the first A. The length falls from six to three. Repeating this operation removes every repeated vertex, so any reachable pair has a path, not merely a walk.
| Walk | Traversals | Endpoints |
|---|---|---|
| A, B, C, A, C, E, F | 6 | A and F |
| A, C, E, F | 3 | A and F |
This deletion explains a shortest-edge-count fact without requiring a search algorithm. A shortest walk between distinct endpoints cannot contain a removable nonempty closed part, since deleting it would use fewer edges. The argument concerns edge count. If every edge carried a nonnegative additive cost, deletion would not increase cost, though it might leave cost unchanged. Negative costs require more care because deleting a negative closed part can raise the total. The current walk model does not edit weights or run that experiment. Its fixed examples support classification and sequence inspection, not a general minimum-cost claim.
A Hamiltonian path visits every vertex exactly once. It need not use every edge. The Euler degree test does not decide this different problem. Likewise, a shortest route between two places need not cover either all vertices or all edges. Specify the requirement before choosing a procedure.
If an unweighted walk repeats a vertex, removing the intervening closed portion gives a shorter walk with the same endpoints. Repeating this yields a path. This explains why shortest unweighted routes need no repetition. Negative edge costs complicate minimum-cost walks because repeated negative cycles can keep reducing cost.
An Euler requirement gives an obligation for every edge, while a Hamiltonian requirement gives an obligation for every vertex. The fixed graph illustrates the difference without changing its records. It has no Euler trail because it has four odd-degree vertices. Yet A, B, C, E, D is a path through five vertices, and A, C, B, D, E, F is a Hamiltonian path through all six. Its five used edges are AC, BC, BD, DE, EF. The unused AB and CE do not violate vertex coverage. They are irrelevant to that requirement once all vertices appear once.
A Hamiltonian cycle would add a return to the starting vertex after visiting all vertices once. The base graph cannot have one because F has degree one. A cycle containing F would need one edge to arrive and a different edge to depart, but EF is its only incident edge. This argument excludes a Hamiltonian cycle without excluding a Hamiltonian path, where F can be an endpoint. In any path covering this graph, F must be an endpoint. Degree gives this local restriction, but it does not by itself provide a general Hamiltonian existence test.
Compare the five-vertex graph made from two triangles sharing A, with edges AB, BC, CA, AD, DE, EA. It has the Euler circuit A, B, C, A, D, E, A because all degrees are even and all vertices are connected. It also has the Hamiltonian path B, C, A, D, E. The Euler circuit uses six edges and repeatedly visits A; the Hamiltonian path uses four edges and visits A once. Both routes solve their own covering problem. Their coexistence does not make them interchangeable, because their permission to repeat vertices differs.
That same two-triangle graph has no Hamiltonian cycle. Removing A separates B and C from D and E. A cycle through all five vertices would have to pass between the triangles and later return, yet their only common connection is A. It would therefore need to revisit A before completing the cycle, contrary to the vertex rule. This gives a structural explanation rather than a failed drawing attempt. The Euler circuit has no such obstacle because its rule allows repeated visits to A as long as each connecting edge is new.
A different obstruction appears in the four-vertex star with center A and edges AB, AC, AD. Each leaf has degree one. Any Hamiltonian path would need B, C, and D as endpoints, since a leaf cannot occupy an intermediate position. A path has only two endpoints, so none exists. The same graph has four odd vertices and thus no Euler trail either. These are separate proofs of separate failures. An impossibility test should identify which object must repeat or which obligation cannot be met, rather than borrowing a familiar test from another covering problem.
| Requirement | Witness or obstruction |
|---|---|
| Euler circuit | A, B, C, A, D, E, A |
| Hamiltonian path | B, C, A, D, E |
| Hamiltonian cycle | No; A is the only connection between triangles |
A practical route can demand something else again. If inspecting all seven links permits retracing, a walk may cover the base graph even though no Euler trail exists. For example A, B, C, A, B, D, E, C, E, F covers all seven edges with some repeats. That is a coverage witness, not a proof that its nine traversals are minimal. Costs, allowed starting locations, and a required return would alter the optimization question. These examples establish exact consequences of stated edge records. They do not certify that a map omits no roads or that every recorded road is currently usable.
A triangle A-B-C-A has an extra edge C-D. Which vertices must be endpoints of an Euler trail? Give one trail.
Only the extra edge changes the triangle's degree parity.
| Vertex | Degree |
|---|---|
| A | 2 |
| B | 2 |
| C | 3 |
| D | 1 |
C has degree 3 and D has degree 1; A and B each have degree 2. The endpoints must be C and D. One trail is D, C, A, B, C. It repeats C but uses every edge once, so it is not a path under our definition.
A delivery route must visit each of four addresses once. Does an Euler-trail test answer whether this is possible?
What objects does the route have to cover?
| Requirement | Graph problem |
|---|---|
| Use every road once | Euler trail |
| Visit each address once | Hamiltonian path |
| Reach one address with fewest links | Unweighted shortest path |
No. The addresses are vertices, so the requirement is a Hamiltonian path if the route may start and end at different addresses. Euler trails cover edges. Neither label includes time windows, parcel loads, or return-to-depot requirements unless added explicitly.
Selected reference passages support the definitions and algorithms below. The networks, explanations, and implementations are original. Terminology and assumptions are stated within each lesson; source review is not an independent audit of this course. Optional links are not runtime dependencies.
Graph representations, degree, trees, BFS and DFS. This course explicitly reserves path for a walk without repeated vertices; the reference uses a different path convention.
Selected degree-parity and connectivity checks for existence of an undirected Euler trail. The reference calls it an Eulerian path; our course distinguishes trails from vertex-simple paths.