"Get from A to E" can mean several different things depending on whether backtracking is allowed, whether a vertex can be visited twice, or whether the journey is even supposed to end somewhere new. Graph theory has one word for each of those variations, and mixing them up is one of the most common early mistakes -- worth pinning down cleanly before algorithms later in this course (breadth-first search, Dijkstra's algorithm, Euler trails) each depend on a specific one of these.
Think of a walk as a stroll where doubling back is completely fine -- you can walk the same street twice, or pass the same corner three times, nobody's counting. A trail is that same stroll with one rule added: never walk down the identical street twice, though you're still free to pass through the same corner more than once if a different street brings you back there. A path tightens it once more: never revisit the same corner at all -- every stop on the route is a place you haven't already been. A cycle is a path that comes home: the same never-repeat-a-corner rule, except the very last stop is allowed to be the very first one, closing the loop.
A walk is any sequence of vertices connected edge by edge, with no restriction at all -- an edge may be reused, and a vertex may be revisited, any number of times. A trail is a walk that never reuses the same edge twice, though it may still revisit a vertex (passing through it on two different edges). A path is stricter still: no vertex may repeat, which automatically forbids any edge from repeating too, since revisiting an edge would mean revisiting one of its endpoints. Every path is a trail, and every trail is a walk, but not the reverse -- each restriction is a stronger requirement than the one before it.
A cycle starts and ends at the same vertex, uses at least three distinct edges, and otherwise behaves like a path: no vertex besides the shared start/end repeats anywhere in between. That "closes up" property is the one thing distinguishing a cycle from an ordinary path, and it matters immediately once a graph has one: a graph containing a cycle has more than one way to reach some pair of vertices, while a cycle-free graph never does.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
Every path is automatically also what?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
A path does not need to return to its starting vertex, so it is not automatically a cycle.
Component is an unrelated connectedness concept, not implied by being a path.
Why
No repeated vertex automatically forbids a repeated edge too, so every path is a trail, and every trail is a walk.
From Discrete Mathematics I — Logic, Proof, and Structure
On edges A-B, B-C, C-A, A-D, classify the sequence A, B, C, A, D.
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Check the edges used: A-B, B-C, C-A, A-D are all distinct, so no edge repeats.
Vertex A appears twice in the sequence, which disqualifies it from being a path.
Every consecutive pair (A,B), (B,C), (C,A), (A,D) is a real edge in the list.
Why
The four edges used are distinct (a trail), but vertex A appears twice, so it is not a path.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
Why can a tree-shaped (branching, no loop) graph never contain a cycle?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
A tree is, in fact, always connected -- disconnection is unrelated to why it lacks cycles.
Trees can have any number of vertices -- vertex count is not the reason cycles are excluded.
Why
Any branch of a tree ends at a leaf of degree 1, and a cycle requires every vertex along it to have two distinct edges within the loop -- a leaf cannot supply that.
From Discrete Mathematics I — Logic, Proof, and Structure
Edges: A-B, B-C, B-D. Is this graph acyclic?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Three edges arranged as a branching star, not a closed loop, contain no cycle -- edge count alone does not decide this.
High degree at one vertex does not by itself create a cycle -- A, C, D each only connect to B and nowhere else.
Why
This is a star shape: A, C, D each have degree 1, so no path leaving them can return without immediately reusing the one edge just crossed.
Enumerate walks and spot which ones repeat a vertex
Pick a start and end vertex, set the walk length k, and look at the listed walks below the matrix -- which ones revisit a vertex partway through, and which ones don't?
Loading interactive…
Walk, trail, path, or cycle?
Sort each described vertex sequence by the strongest label that correctly applies to it.
Loading interactive…
Worked example
Classifying a given sequence
-
1
In a graph with a 4-cycle A-B-C-D-A, classify the sequence A, B, C, B, D as precisely as possible.
-
2
Check for a repeated vertex first, since that's the strongest restriction: B appears twice, at positions 2 and 4.
-
3
A repeated vertex rules out "path" and "cycle" (both forbid it), so check whether an edge repeats: the two edges touching the repeated B are AB then BC (arriving) and BD (leaving) -- three different edges, none reused.
-
4\boxed{\text{A trail, but not a path}}
Loading interactive…
Worked example
Deciding whether a cycle exists in a small graph
-
1
A graph has edges AB, BC, CD. Does this graph contain a cycle?
-
2
A cycle needs to return to its own starting vertex using at least three distinct edges, with nothing else repeated in between.
-
3
Trace every possible route: starting at A, the only way forward is A\to B\to C\to D, and D has no edge back to A (or anywhere else) to close the loop.
-
4\boxed{\text{No cycle} - \text{this graph is a straight path, } A\text{ to }D}
Worked example
Recognizing why every cycle is not a path
-
1
A student says "a cycle is just a special kind of path." Is that accurate?
-
2
Compare the two definitions directly rather than relying on intuition: a path forbids any vertex from repeating, full stop -- including the start and end.
-
3
A cycle's start and end vertex are the same vertex, which is exactly the one repetition a path's definition disallows.
-
4\boxed{\text{No} - \text{a cycle fails the path definition at its own closing step}}
A cycle is better described as a path's closed cousin: identical rule everywhere except that one deliberate exception at the finish.
Where this goes next
Algorithm design
Every traversal algorithm this course builds later -- breadth-first search, depth-first search, Dijkstra's shortest-path algorithm -- has to decide what to do about a vertex it's already seen, and the walk/trail/ path distinction is exactly the vocabulary that decision gets described in. A shortest path, by definition, never benefits from revisiting a vertex, which is precisely why shortest-path algorithms search for paths, never merely walks.
Check your understanding (counts toward your progress)
A sequence uses 5 distinct edges and visits 6 distinct vertices, never repeating any vertex. What is it?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
'Walk' undersells this -- no vertex repeats, which is the strongest possible claim.
Since no vertex ever repeats, it automatically qualifies as a path, the strongest of the three labels.
'Never repeating any vertex' is exactly the path condition -- that's enough information.
Why
No repeated vertex is precisely the definition of a path, which is automatically also a trail and a walk.
Start from the strictest possible label and check whether the 'no repeated vertex' condition it requires is actually satisfied here.
A student claims 'every walk is also a trail.' Is this correct?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
The containment runs the other direction: every trail is a walk, not every walk is a trail.
Length isn't what separates these two categories.
Directedness isn't relevant to this particular relationship.
Why
A walk allows a repeated edge; a trail specifically disallows one. A walk that happens to repeat an edge is a walk but not a trail.
Think of a specific walk that reuses one edge, and check whether a trail's own definition would still allow it.
A courier's route visits the same intersection twice, arriving each time by a different street. Which best models this in graph terms?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
A path can't revisit a vertex -- the intersection was visited twice.
This is exactly what a trail models -- it just isn't the strictest label available.
A cycle needs to end back where it started -- nothing here says the route returns to its first intersection.
Why
Revisiting a vertex (the intersection) via two different edges (streets) is a trail, but the repeated vertex disqualifies it from being a path.
Identify which graph object corresponds to the intersection and which to the street, then check separately whether either one repeats.
Which of these is the loosest, most permissive of the three terms -- walk, trail, path?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Walk has no restriction at all; trail adds a no-repeated-edge rule; path adds the further no-repeated-vertex rule -- each is a stricter subset of the one before it.
Practice: Telling walks, trails, and paths apart (4 problems · doesn’t affect your progress)
A sequence repeats the same edge twice. What is the strongest label -- walk, trail, or path -- that can still apply?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Repeating an edge is exactly what disqualifies a sequence from being a trail (or a path, which is even stricter) -- only 'walk' still applies.
Check whether this sequence could still qualify as a trail before settling for the loosest possible label.
Walk
A sequence never repeats a vertex. Is it automatically a trail as well as a path?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Never repeating a vertex also guarantees never repeating an edge (repeating an edge would force one of its endpoints to repeat), so every path is a trail.
Yes -- a path is automatically a trail too
A path visits 8 distinct vertices in a row. How many edges does it use?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
A path through k vertices uses exactly k-1 edges, one between each consecutive pair: 8-1=7.
Correct answer
Also accepted:
Why
Count one edge between each consecutive pair of the 8 vertices in the path.
A delivery route revisits the same warehouse twice, using two different roads to get there each time, and never repeats a road. What's the best label?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
The warehouse (a vertex) repeats, ruling out 'path,' but no road (edge) repeats, which is exactly what keeps it a trail.
Identify which repeats here -- the vertex (the warehouse) or the edge (the road) -- and which one doesn't.
Match that specific pattern of repeats against the trail-versus-path distinction.
Trail, not a path
Check your understanding (counts toward your progress)
How does a cycle differ from a path, precisely?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
A closed walk can repeat vertices and edges freely in between -- a cycle can't.
A cycle only needs to close on itself; it says nothing about visiting every vertex in a larger graph.
They differ in exactly one place -- whether the final vertex is allowed to equal the first.
Why
A cycle follows every rule a path does (no repeated vertex) except at the very last step, where returning to the start is required rather than forbidden.
Compare a cycle's definition to a path's rule one clause at a time, rather than treating the two as either identical or unrelated.
A graph has edges AB, BC, CA, CD. Does it contain a cycle, and if so, which vertices form it?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
D only connects to C with a single edge -- it has no way back into the loop, so it isn't part of the cycle.
B is part of the triangle, not D -- check which three vertices actually close a loop.
Why
A-B-C-A uses the three edges AB, BC, CA and returns to its own start -- a genuine cycle. D hangs off C with no return path, so it's outside the cycle.
Trace which edges actually form a closed loop back to their own starting vertex, and separately check whether D has any way back into that loop.
A student says: 'if a graph has no cycles, it must be disconnected.' Is this correct?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
A tree is a direct counterexample: connected, and with no cycles at all.
Vertex count has nothing to do with this claim.
A tree can have any number of vertices and still stay both connected and cycle-free.
Why
Connectedness and cycle-freeness are independent properties -- a tree is the standing counterexample that a graph can be both connected and completely free of cycles.
Think of the standing example of a graph that is connected and has zero cycles.
Check whether that example contradicts the student's claim.
A graph consists only of the edges AB, BC, CD -- no edge closes back to A. Does this graph contain a cycle?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
A path from A to D isn't a cycle -- a cycle must return to its own starting vertex.
Why
With no edge returning to any vertex already visited, this is a straight path from A to D, not a cycle.
Practice: Cycles, and how they differ from paths (4 problems · doesn’t affect your progress)
What is the one thing a cycle does that a path never does?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
A cycle's defining feature beyond an ordinary path is closing back to its own start.
Returns to its own starting vertex
A cycle uses 9 distinct vertices before closing back to its start. How many edges does it use?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
A cycle through k vertices uses k edges -- one between each consecutive pair, plus one closing edge back to the start.
Correct answer
Also accepted:
Why
A connected graph on n vertices has exactly n-1 edges. Can it contain a cycle?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
A connected graph with exactly n-1 edges IS a tree by the equivalent-characterizations theorem, and a tree contains no cycle.
Recall which structure a connected graph with exactly n-1 edges already is, by the equivalent-characterizations theorem.
No -- that's exactly the edge count of a tree, which is cycle-free
Two distinct, edge-disjoint paths connect the same pair of vertices A and D. What must the graph contain?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Traversing the first path from A to D and the second path backward from D to A traces a closed loop that never reuses an edge -- a cycle.
Picture tracing the first path from A to D, then continuing back along the second path from D to A.
Ask what that combined route forms, given it never repeats an edge.
A cycle