A route through a graph may repeat a vertex, repeat an edge, return to its starting point, or help us reach every vertex. Each change gives the route a different name. Classify routes from definitions, not memory, by checking exact sequences in a fixed undirected graph and testing connectivity. The GATE CS Exam Preparation hub places this topic in the broader study journey.
1. Fix the graph and the notation before classifying a route
Use the undirected simple graph \(G=(V,E)\), where
\(V=\{A,B,C,D,E,F\}\)
and
\(E=\{AB,AC,BC,BD,CD,CE,DE,EF\}\).
A proposed vertex sequence is a walk only when every consecutive pair is joined by an edge in \(E\). Since the graph is undirected, \(BC\) and \(CB\) mean the same edge traversed in opposite directions. The length of a walk is the number of edge traversals, not the number of vertices written. Thus, \(A-C-E-F\) contains four written vertices but uses the three edges \(AC,CE,EF\), so its length is 3. By contrast, \(A-D\) is not a walk because \(AD\) is absent. This edge-list-first habit also prevents a plausible sketch from hiding an invalid step in the sequence.
The degrees provide a quick check on the drawing: \(\deg(A)=2\), \(\deg(B)=3\), \(\deg(C)=4\), \(\deg(D)=3\), \(\deg(E)=3\), and \(\deg(F)=1\). Their sum is \(2+3+4+3+3+1=16=2|E|\), which agrees with the eight undirected edges.
2. Walk, trail, path, closed walk, circuit and cycle
A walk may repeat vertices and edges. A trail is a walk with no repeated edge. A path is a walk with no repeated vertex. Therefore, every path is a trail and every trail is a walk, but neither converse is guaranteed.
For closed routes, use the following precise hierarchy. A closed walk has the same first and last vertex. A circuit is a closed trail. A cycle is a circuit with no repeated vertex except the first vertex appearing again at the end. If a question supplies a different convention for the words circuit and cycle, follow that stated convention.
For example, \(B-C-E-D-B\) uses four distinct edges and repeats only its endpoint \(B\), so it is a length-4 circuit and cycle. The sequence \(C-A-B-C-D-E-C\) is a length-6 circuit but not a cycle. Its edges \(CA,AB,BC,CD,DE,EC\) are distinct, but \(C\) appears at the start, in the middle, and at the end. These local definitions lead naturally to graph-wide ideas such as Euler and Hamiltonian circuits, covered in Graph Theory: Euler, Hamiltonian, Coloring for GATE CS.
3. Worked example: classify five sequences step by step
Use the same decision order every time: validate each consecutive pair, write the traversed edges, count those edges, audit repeated edges, audit repeated vertices, compare the endpoints, and only then classify.
Sequence | Edge list | Length | Repeated vertex? | Repeated edge? | Closed? | Most specific classification |
|---|---|---|---|---|---|---|
\(W1: A-B-C-B-D\) | \(AB,BC,CB,BD\), all pairs valid | 4 | Yes, \(B\) | Yes, undirected edge \(BC\) is used twice | No | Walk only |
\(T1: A-B-C-D-B\) | \(AB,BC,CD,DB\), all pairs valid | 4 | Yes, \(B\) | No | No, \(A\ne B\) | Trail, not path |
\(P1: A-C-E-F\) | \(AC,CE,EF\), all pairs valid | 3 | No | No | No | Path, therefore also trail and walk |
\(C1: B-C-E-D-B\) | \(BC,CE,ED,DB\), all pairs valid | 4 | Only endpoint \(B\) | No | Yes | Circuit and cycle, therefore also closed trail and closed walk |
\(CW1: A-B-C-B-A\) | \(AB,BC,CB,BA\), all pairs valid | 4 | Yes, \(A\) and \(B\) | Yes, \(AB\) and \(BC\) are each used twice | Yes | Closed walk, not circuit |
The edge audit is decisive. In \(W1\), writing \(BC\) and then \(CB\) does not create two edges because the graph is undirected. In \(T1\), vertex \(B\) repeats, but the edges \(AB,BC,CD,DB\) do not, so the sequence remains a trail. In \(C1\), the matching endpoints make the trail closed, and no internal vertex repeats, so it satisfies both circuit and cycle.
Keep the containment directions fixed:
\(\text{path} \Rightarrow \text{trail} \Rightarrow \text{walk}\)
\(\text{cycle} \Rightarrow \text{circuit} \Rightarrow \text{closed walk}\)
The reverse implications do not generally hold.
4. Connected graphs, reachability, components and a bridge
Two vertices \(u\) and \(v\) are connected when some path joins them. An undirected graph is connected when every pair of vertices is connected. To test \(G\), start at \(A\) and find one shortest path to every vertex:
Vertex | One shortest path from \(A\) | Distance |
|---|---|---|
\(A\) | \(A\), the length-0 path | 0 |
\(B\) | \(A-B\) | 1 |
\(C\) | \(A-C\) | 1 |
\(D\) | \(A-B-D\) | 2 |
\(E\) | \(A-C-E\) | 2 |
\(F\) | \(A-C-E-F\) | 3 |
All six vertices are reachable from \(A\), so \(G\) is connected. Connected does not mean complete. There is no edge \(AD\), yet the path \(A-B-D\) connects those vertices. Connectivity asks whether some path exists between each pair. It does not require every pair to be adjacent, and it does not require one particular route to visit every vertex.
Now delete only \(EF\). Vertex \(F\) becomes isolated, while \(A,B,C,D,E\) remain mutually reachable. The new graph has exactly two connected components, \(\{A,B,C,D,E\}\) and \(\{F\}\). In the original graph, \(EF\) is therefore a bridge because removing it increases the component count from 1 to 2.
5. Common traps and the correction for each
Counting written vertices as the length. List the edges first. \(B-C-E-D-B\) has five written vertices but four traversed edges. Likewise, \(A-D\) fails before classification because \(AD\) is missing.
Treating a repeated vertex as a repeated edge. Audit vertex identity and edge identity separately. \(T1\) repeats \(B\) but no edge, so it is still a trail.
Calling every closed walk a circuit. Returning to the start is not sufficient. \(CW1\) repeats both \(AB\) and \(BC\), so it is not a circuit.
Reading connected as complete. Test whether every vertex is reachable by some path. A route does not itself have to visit all vertices for the graph to be connected.
Reversing \(u-v\) is valid here because \(G\) is undirected, but a directed graph requires the arc in the direction you traverse it.
6. How exam-style questions test these ideas
Questions can ask you to classify a supplied sequence, calculate its length, decide whether deleting an edge disconnects a graph, or count connected components. Here are four rapid checks from \(G\):
\(A-D\) is not a walk because \(AD\) is absent.
\(A-C-D-B-C\) is a trail but not a path. Its edges \(AC,CD,DB,BC\) are distinct, while vertex \(C\) repeats.
\(B-A-C-B\) is a length-3 circuit and cycle.
Deleting \(EF\) leaves 2 components.
Practise adjacent Graph Theory problems with Graph Theory MCQs: 12 Solved Euler, Coloring, Trees, then attempt a mixed set under a time limit.
A walk or path describes a vertex-edge sequence. For algorithmic traversal using search procedures, study Graph Algorithms: BFS, DFS and Shortest Paths separately. Route classification checks the sequence itself, while BFS and DFS specify procedures for visiting vertices.
7. The short version and the next study step
For any sequence, validate consecutive edges, count edge traversals, check repeated edges, check repeated vertices, and compare the endpoints. For connectivity, test reachability. Remember: paths are trails, trails are walks, cycles are circuits, and circuits are closed walks.
Now classify \(C-A-B-C-D-E-C\) without looking back. Then remove \(EF\) and list the components. If you want a structured route through the wider subject, continue with GATE Guidance by Sanchit Sir. Your concrete next action is simple: draw the edge list beside every proposed sequence before naming it, then state the reason in one line.
