Comprehensive Study Notes on Graph Theory, Traversal Algorithms, Bipartiteness, and Topological Sorting
Foundations of Graph Theory and Graph Representations
Formal Definition of a Graph:
A graph is a non-linear data structure denoted as .
represents a finite, non-empty set of vertices (also called nodes).
represents a set of edges, where each edge corresponds to a connection between a pair of vertices such that .
Core Graph Terminology:
Adjacent / Neighbours: Two vertices and are adjacent (or neighbours) if they are directly connected by an edge .
Incident: An edge is said to be incident to both vertex and vertex .
Degree of a Vertex (): The total number of edges connected to a vertex .
Directed vs. Undirected Graphs:
In an undirected graph, edges are bidirectional unordered pairs; the edge is identical to .
In a directed graph (digraph), edges are ordered pairs with direction (arrows). Each vertex possesses two distinct degree metrics:
In-degree: The number of incoming edges directed into the vertex.
Out-degree: The number of outgoing edges directed away from the vertex.
Path: A path is an alternating sequence of vertices such that each consecutive pair is joined by an edge .
Distance: The distance between two vertices and is defined as the minimum number of edges on any path connecting to .
Cycle: A path in which the starting and ending vertices coincide ( with ) and the first vertices are distinct.
Loop (Self-loop): An edge that connects a vertex directly to itself.
Connected Graph: An undirected graph is connected if there exists a valid path between every pair of vertices and .
Connected Components: Maximal connected subgraphs within a disconnected graph.
Tree: An undirected graph that is connected and contains no cycles (acyclic).
Weighted Graph: A graph in which each edge has an associated numerical value (weight or cost).


Linked Lists and Trees as Restricted Directed Acyclic Graphs (DAGs):
A binary tree is a specialized graph characterized by:
Being an unweighted, directed acyclic graph (DAG).
Having an in-degree of at most for every node.
Having an out-degree of at most for every node.
Having a unique designated root node with in-degree , from which exactly one directed path leads to every other node.
A singly linked list is a specialized graph characterized by:
Being an unweighted DAG.
Having an in-degree of at most and an out-degree of at most for all nodes.


Real-World Graph Modeling:
Web Pages and Hyperlinks: Web pages represent vertices; directed hyperlinks between pages represent directed edges.
Program Call Graphs: Methods/functions represent vertices; function calls represent directed edges.
Road Networks: Intersections/locations represent vertices; streets represent edges (undirected or directed based on one-way streets).
Airline Flight Systems: Airports represent vertices; non-stop flights represent edges, often weighted by distance, duration, or ticket price.
Social Networks: Individual user profiles represent vertices; mutual friendships represent undirected edges.
Academic Prerequisites: Courses represent vertices; prerequisite requirements represent directed edges, forming a DAG.
Mazes: Decision junctions represent vertices; accessible corridors represent edges.
Internet Backbone: Individual routers or IP addresses represent vertices; physical optical/cable data lines represent edges.

Path Optimization Objectives:
Path Existence: Determining if any valid path connects vertex to vertex .
Hop-Count Minimization: Finding a path that minimizes the total number of intermediate edges (unweighted shortest path).
Cost Minimization: Finding a path that minimizes the cumulative sum of edge weights (weighted shortest path).
Graph Storage Representations:
Adjacency Matrix:
A 2D boolean or integer array of size , where vertices are indexed from to .
An entry if an edge ; otherwise, .
For undirected graphs without self-loops, the adjacency matrix is symmetric along its main diagonal (), and all diagonal entries are .
Space Complexity: .
Edge Lookup / Insertion / Deletion Time: .
Finding All Neighbours of Vertex : , as the entire row must be scanned.
Adjacency List:
An array or map of linked lists/dynamic arrays of size .
Each vertex index points to a list containing all vertices directly adjacent to .
Space Complexity: for directed graphs; which simplifies to for undirected graphs.
Edge Lookup Time: .
Finding All Neighbours of Vertex : .
Trade-Off Summary:
The adjacency matrix is preferred for dense graphs where , or when instant edge-existence queries are essential.
The adjacency list is vastly superior for sparse graphs where , saving substantial memory and allowing efficient neighbour iteration.
Graph Traversal Fundamentals
The Objective of Traversal:
Starting from a designated initial vertex , systematically visit every reachable vertex in the graph exactly once.
Traversal algorithms explore connected components and construct spanning forests over the graph.
Cycle Handling via the Visited Mark:
Unlike trees, graphs may contain cycles. Without preventive mechanisms, an algorithm exploring a cycle such as would enter an infinite loop.
To prevent cycling, every traversal maintains a boolean array or lookup table
visited[]of size .A vertex is marked as visited upon discovery; once marked, it is never processed as a new vertex again.
Deterministic Tie-Breaking Rule:
When a vertex has multiple unvisited adjacent neighbours, all canonical tracing follows strict alphabetical or ascending numerical order.
General Runtime Complexity Derivation:
For both Breadth-First Search (BFS) and Depth-First Search (DFS), using an adjacency list yields a time complexity of:
Derivation:
Each vertex is placed into the tracking structure (queue or stack) and removed at most once: .
When processing a vertex, all its incident edges are inspected. Across the entire traversal, every directed edge is examined once; every undirected edge is examined twice (once from each endpoint).
Sum of degrees formula (Handshaking Lemma):
Therefore, the total edge exploration operations take .
Combined time equals .
If an adjacency matrix is used instead, scanning all potential neighbours for every vertex requires checking an entire row of length , resulting in a time complexity of:
Breadth-First Search (BFS)
Core Philosophy:
Explores the graph layer by layer, expanding outward like ripples in water.
First processes the root/start node (Level ), then all immediate neighbours of the start node (Level ), then all neighbours of Level nodes (Level ), and so forth.
Explores paths in parallel breadth-wise before advancing to deeper levels.
Queue Mechanism (FIFO):
Operates using a First-In, First-Out (FIFO) Queue data structure.
ENQUEUE(x): Inserts element at the rear.DEQUEUE(): Removes and returns the element at the front.Vertices discovered earlier are dequeued earlier, enforcing strict level-by-level processing.
Critical Invariant: A vertex must be marked as visited immediately upon being enqueued (not when dequeued). This prevents the same vertex from being inserted into the queue multiple times by different neighbours.
Queue-Based BFS Algorithm: ```text BFS(G, s): for each vertex u in V: visited[u] = false dist[u] = infinity parent[u] = null
visited[s] = true dist[s] = 0 Q.enqueue(s)
while Q is not empty: v = Q.dequeue() process(v) for each neighbour u of v (in alphabetical order): if visited[u] == false: visited[u] = true dist[u] = dist[v] + 1 parent[u] = v Q.enqueue(u) ```
Comprehensive Step-by-Step BFS Trace on a 7-Vertex Graph:
Graph topology consists of vertices with edges: .
Start vertex is .

Step 0 (Initialization):
Mark visited. Distance .
Queue = [ A ](front = rear = ).Output = [].
Step 1 (Process A):
Dequeue . Output:
A.Inspect neighbours of in alphabetical order: .
is unvisited: mark visited, set , enqueue .
is unvisited: mark visited, set , enqueue .
Queue = [ B, C ].Output = [ A ].
Step 2 (Process B):
Dequeue . Output:
B.Inspect neighbours of : .
is already visited: skip.
is unvisited: mark visited, set , enqueue .
is unvisited: mark visited, set , enqueue .
Queue = [ C, D, E ].Output = [ A, B ].
Step 3 (Process C):
Dequeue . Output:
C.Inspect neighbours of : .
is already visited: skip.
is already visited (currently in queue): skip.
is unvisited: mark visited, set , enqueue .
Queue = [ D, E, F ].Output = [ A, B, C ].
Step 4 (Process D):
Dequeue . Output:
D.Inspect neighbours of : .
is already visited: skip.
No vertices added.
Queue = [ E, F ].Output = [ A, B, C, D ].
Step 5 (Process E):
Dequeue . Output:
E.Inspect neighbours of : .
is already visited: skip.
is already visited: skip.
is unvisited: mark visited, set , enqueue .
Queue = [ F, G ].Output = [ A, B, C, D, E ].
Step 6 (Process F):
Dequeue . Output:
F.Inspect neighbours of : .
is already visited: skip.
is already visited (currently in queue): skip.
No vertices added.
Queue = [ G ].Output = [ A, B, C, D, E, F ].
Step 7 (Process G):
Dequeue . Output:
G.Inspect neighbours of : .
Both and are already visited: skip.
Queue = [ ](empty).Output = [ A, B, C, D, E, F, G ].Traversal terminates.
BFS Tree and Shortest Path Property:
Levels and Parent Relationships:
Level (): (Parent: none)
Level (): (Parent: ), (Parent: )
Level (): (Parent: ), (Parent: ), (Parent: )
Level (): (Parent: )
Shortest Path Retrieval:
BFS guarantees that the level number equals the minimum hop distance from the start node.
To reconstruct the unweighted shortest path from start node to target , follow parent pointers in reverse:
Inverting yields the optimal path: , requiring exactly edges.
BFS Characteristics:
Time Complexity: with adjacency list; with adjacency matrix.
Space Complexity: to maintain the queue and visited array.
Primary Applications:
Unweighted single-source shortest paths.
Level-order tree traversals.
Degrees of separation in social networks ("friends of friends").
Web crawlers discovering documents by hop distance.
Connected component identification.
Testing for bipartiteness / 2-colourability.
Depth-First Search (DFS)
Core Philosophy:
Explores the graph by advancing along a single path as deeply as possible until a dead end is reached.
Upon encountering a vertex with no unvisited neighbours, it backtracks to the most recent vertex with unexplored options.
Resembles exploring a maze by following a path to its conclusion before retracing steps.
Stack Mechanism (LIFO):
Operates using a Last-In, First-Out (LIFO) Stack data structure, implemented explicitly or via system call stack (recursion).
PUSH(x): Places element onto the top of the stack.POP(): Removes and returns the element from the top of the stack.TOP(): Inspects the current top element without removing it.The stack stores the active path from the search root to the current frontier node. Backtracking corresponds directly to a
POP()operation.
DFS Algorithms (Recursive and Iterative):
Recursive Implementation:
text DFS_recursive(u): visited[u] = true print(u) for each neighbour v of u (in alphabetical order): if visited[v] == false: DFS_recursive(v)
Iterative Implementation (Using Explicit Stack): ```text DFS_iterative(G, s): visited[s] = true print(s) S.push(s)
while S is not empty: v = S.top() if v has an unvisited neighbour u: visited[u] = true print(u) S.push(u) // advance deeper else: S.pop() // backtrack```
Comprehensive Step-by-Step DFS Trace on the 7-Vertex Graph:
Same graph: vertices , start at , alphabetical tie-breaking.
Step 0:
Visit , output:
A.Stack = [ A ](bottom to top).Step 1:
Top is . First unvisited neighbour is .
Visit , output:
B.Stack = [ A, B ].Step 2:
Top is . Neighbours are (visited), (unvisited), (unvisited).
First unvisited is . Visit , output:
D.Stack = [ A, B, D ].Step 3:
Top is . Neighbour is already visited.
Dead end reached at . Pop . Stack reverts to
[ A, B ].Top is now . Next unvisited neighbour is .
Visit , output:
E.Stack = [ A, B, E ].Step 4:
Top is . Neighbours are (visited), (unvisited), (unvisited).
First unvisited is . Visit , output:
C.Stack = [ A, B, E, C ].Step 5:
Top is . Neighbours are (visited), (visited), (unvisited).
First unvisited is . Visit , output:
F.Stack = [ A, B, E, C, F ].Step 6:
Top is . Neighbours are (visited), (unvisited).
First unvisited is . Visit , output:
G.Stack = [ A, B, E, C, F, G ].Step 7 (Backtracking Phase):
Top is . Neighbours are both visited. Dead end:
Pop G. Stack:[ A, B, E, C, F ].Top is . All neighbours visited. Dead end:
Pop F. Stack:[ A, B, E, C ].Top is . All neighbours visited. Dead end:
Pop C. Stack:[ A, B, E ].Top is . All neighbours visited. Dead end:
Pop E. Stack:[ A, B ].Top is . All neighbours visited. Dead end:
Pop B. Stack:[ A ].Top is . All neighbours visited. Dead end:
Pop A. Stack:[ ](empty).Traversal complete.
Final DFS Visit Order: .
Edge Classification in DFS:
Tree Edges: Edges traversed forward to discover an unvisited vertex for the first time. Here: .
Back Edges: Edges connecting the current vertex to an ancestor already present on the active stack. Here: and .
Fundamental Theorem of DFS on Undirected Graphs:
In any DFS forest of an undirected graph , every edge of is either a tree edge or a back edge. Cross edges and forward edges cannot exist in an undirected DFS.
Ancestor-Descendant Relationship Theorem: If is a depth-first search tree of graph and is an edge in but not in , then either is an ancestor of or is an ancestor of in .
Cycle Detection: The presence of at least one back edge rigorously proves the existence of a cycle (e.g., back edge defines cycle ).


DFS Characteristics:
Time Complexity: with adjacency list; with adjacency matrix.
Space Complexity: in the worst-case (a linear degenerate path).
Primary Applications:
Maze solving and game backtracking.
Cycle detection in both directed and undirected graphs.
Topological sorting of DAGs.
Connectivity and biconnectivity analysis.
Finding strongly connected components (Kosaraju's and Tarjan's algorithms).
Comparative Analysis: BFS versus DFS
Direct Comparison Table:
Feature | Breadth-First Search (BFS) | Depth-First Search (DFS) |
|---|---|---|
Full Name | Breadth-First Search | Depth-First Search |
Underlying Data Structure | Queue (FIFO: First-In, First-Out) | Stack (LIFO: Last-In, First-Out) or Call Stack |
Exploration Trajectory | Level by level (wide exploration) | Deep along a branch until dead end, then backtrack |
Generated Spanning Tree | Short and broad (shallow height) | Long and narrow (deep branches) |
Order on Example Graph | ||
Shortest Path (Unweighted) | Guaranteed to find minimum hop path | Not optimal; finds arbitrary reachable path |
Shortest Path (Weighted) | Not optimal in general | Not optimal in general |
Time Complexity (List) | ||
Time Complexity (Matrix) | ||
Space Complexity | (bounded by max width of graph) | (bounded by max depth of recursion) |
Path Reconstruction | Requires storing explicit predecessor array | Directly recorded by current stack contents |
Canonical Applications | Shortest paths, peer-to-peer networks, web crawlers | Topological sorting, maze solving, cycle detection |
Bipartite Graphs and 2-Colouring
Formal Definition:
A graph is bipartite if its vertex set can be partitioned into two disjoint subsets and ( and ) such that every edge connects a vertex in to a vertex in .
No edge may join two vertices belonging to the same partition subset: for all , .

Equivalence to 2-Colourability:
A graph is 2-colourable if each vertex can be assigned one of two colours (e.g., RED and BLUE) such that no two adjacent vertices share the same colour.
Equivalence Statement: A graph is bipartite if and only if it is 2-colourable:
Group maps to all RED vertices; Group maps to all BLUE vertices.

The Odd-Cycle Theorem (The Golden Rule):
A graph is bipartite if and only if it contains no odd-length cycles.
Proof Intuition:
In any 2-colouring, traversing an edge forces an alternation between RED and BLUE.
To traverse a cycle and return to the starting vertex with its original colour, the traversal must execute an even number of colour alternations.
If a cycle has an odd length , starting at RED leads to alternating colours that require the -th vertex to be RED, while also being adjacent to the initial RED vertex, creating a contradiction.
Corollaries:
All Trees are Bipartite: Trees contain zero cycles; thus, they trivially contain no odd cycles and are always bipartite.
Even Cycles are Always Bipartite: Any simple cycle of length () can be successfully 2-coloured.
Triangles () and Complete Graphs () are Never Bipartite: A triangle contains edges (odd); complete graphs contain triangles.


BFS 2-Colouring Algorithm:
BFS naturally classifies vertices by distance from the root. If a graph is bipartite, all vertices at even levels must belong to one colour class, and all vertices at odd levels must belong to the other.
Algorithm Logic:
Initialize all vertices as uncoloured.
For every connected component (to handle disconnected graphs):
Pick an uncoloured vertex , assign it colour
RED, and enqueue it.While the queue is not empty:
Dequeue vertex .
For each neighbour of :
If is uncoloured: assign and enqueue .
If is already coloured with : valid, continue.
If is already coloured with the same colour as : Conflict detected. Terminate immediately; the graph is not bipartite.
If the queue empties with no conflicts detected across all components, the graph is bipartite.
Algorithm Pseudocode: ```text isBipartite(G): for each vertex u in V: colour[u] = NONE
for each vertex s in V: if colour[s] == NONE: colour[s] = RED Q.enqueue(s)
while Q is not empty: v = Q.dequeue() for each neighbour u of v: if colour[u] == NONE: colour[u] = opposite(colour[v]) Q.enqueue(u) else if colour[u] == colour[v]: return NOT_BIPARTITEreturn BIPARTITE ```
Complexity: Identical to standard BFS: time and space.
Worked 2-Colouring Trace 1 (Bipartite Graph):
Graph with vertices .
Trace starting from (assign RED):

Dequeue (RED): Neighbours are uncoloured; colour all
BLUE, enqueue .Dequeue (BLUE): Neighbour is RED (valid); neighbour is uncoloured; colour
RED, enqueue .Dequeue (BLUE): Neighbour is RED (valid); neighbour is RED (valid); neighbour is uncoloured; colour
RED, enqueue .Dequeue (BLUE): Neighbour is RED (valid); neighbour is RED (valid).
Dequeue (RED): Neighbour is BLUE (valid); neighbour is BLUE (valid).
Dequeue (RED): Neighbour is BLUE (valid); neighbour is BLUE (valid).
Queue is empty. No conflicts occur.
Conclusion: Graph is bipartite.
Partition sets:
All simple cycles ( of length , of length , and outer cycle of length ) are strictly even.

Worked 2-Colouring Trace 2 (Non-Bipartite Odd Cycle):
5-cycle graph with vertices forming edges .
Start at : colour
RED, enqueue .Dequeue (RED): Enqueue (
BLUE) and (BLUE).Dequeue (BLUE): Neighbour is RED (valid); colour
RED, enqueue .Dequeue (BLUE): Neighbour is RED (valid); colour
RED, enqueue .Dequeue (RED): Neighbour is BLUE (valid); neighbour is inspected.
is already coloured
RED.Conflict: Edge connects two
REDvertices ().Conclusion: Graph is not bipartite due to the presence of an odd cycle of length .

Quick Bipartite Classification Reference:
Graph Description | Bipartite? | Theoretical Justification |
|---|---|---|
Path graph with 4 vertices () | Yes | Trees have no cycles; paths are trees. |
Cycle graph with 6 vertices () | Yes | Cycle length is even (). |
Cycle graph with 7 vertices () | No | Cycle length is odd (). |
Complete graph on 4 vertices () | No | Contains odd cycles (triangles ). |
Any arbitrary tree | Yes | Acyclic graphs contain zero odd cycles. |
Square with one diagonal added | No | The diagonal splits the square into two triangles (-cycles). |
Topological Sorting of Directed Acyclic Graphs (DAGs)
Formal Definition:
For a directed acyclic graph , a topological sort is a linear ordering of all vertices such that for every directed edge , vertex strictly precedes vertex in the ordering.

Prerequisites and Theoretical Properties:
A graph admits a topological sort if and only if it is a DAG (Directed Acyclic Graph).
Impossibility in Cyclic Graphs: If a graph contains a directed cycle (), then must precede , must precede , and must precede , creating an impossible circular dependency.
Non-Uniqueness: A single DAG typically admits multiple valid topological sorts, each representing a valid sequential execution schedule.

For the DAG shown above, valid topological orders include:
Algorithm 1: Naive In-Degree Elimination:
Compute and store the in-degree of every vertex.
While unvisited vertices remain:
Perform a linear scan over all vertices to find a vertex with (a source/root).
Output .
Remove and all its outgoing edges , decrementing the in-degree of each neighbour .
Complexity: Scanning for a root takes per step over iterations, resulting in time.
Algorithm 2: Optimized In-Degree Algorithm (Kahn's Algorithm with Stack/Queue):
Computes all in-degrees initially in .
Uses an auxiliary container (stack or queue) to store vertices whose in-degree is currently , eliminating repeated linear scans.
Algorithm Logic: ```text TopologicalSort(G): compute in-degree for all v in V initialize Stack S
for each v in V: if in-degree[v] == 0: S.push(v) count = 0 while S is not empty: r = S.pop() output(r) count = count + 1for each neighbour n of r: in-degree[n] = in-degree[n] - 1 if in-degree[n] == 0: S.push(n)if count != |V|:
error "Graph contains a cycle; no topological sort exists"```
Complexity: Every vertex is pushed/popped once, and every edge is decremented once, achieving optimal runtime.
Topological Sorting via DFS:
Topological sorting can also be implemented using DFS.
In a DAG, a vertex finishes exploration (is popped from the recursion stack) only after all its downstream descendants have finished.
Therefore, recording vertices in reverse order of their DFS completion/exit times produces a valid topological sort.
Solved Traversal Problems and Exam Scenarios
Problem 1: Validating BFS Orders on an Undirected Graph:
Graph Topology: Vertices with edges forming levels relative to start vertex :
Level :
Level :
Level :
Level :
Candidate Orders Evaluated:
(a)
(b)
(c)
(d)
Validation Rules:
Rule 1 (Strict Level Order): All Level vertices must precede any Level vertex.
Rule 2 (Parent Queue Order): Within a level, children of the parent dequeued earlier must enter the queue and appear first.
Option Analysis:
Option (a) violates Rule 1: Vertex (Level 2) appears before and (Level 1). Invalid.
Option (c) violates Rule 2: If is dequeued before , discovers , while discovers . Therefore, must precede . Invalid.
Option (d) violates Rule 2: If is dequeued before and , discovers before is discovered. Thus, must precede . Invalid.
Option (b) is fully consistent: Level 1 is ordered . Vertex dequeues first and discovers both and . Enqueueing them as is valid, followed by at Level 3. Valid.
Queue Trace for Option (b):
Step | Dequeue | New Neighbours Enqueued | Queue State (Front to Rear) | Output So Far |
|---|---|---|---|---|
0 | — | Start: enqueue |
|
|
1 |
|
| ||
2 | ( visited) |
|
| |
3 | None ( visited) |
|
| |
4 | None ( visited) |
|
| |
5 | ( visited) |
|
| |
6 | None ( visited) |
|
| |
7 | None |
|
|
Problem 2: Identifying Non-Valid DFS Orders:
Using the same graph starting from vertex , identify which sequence is NOT a valid DFS order:
(a)
(b)
(c)
(d)
Verification Method:
In DFS, the next visited node must be an unvisited neighbour of the current stack top.
If the current top has no unvisited neighbours, it must be popped, and the next node must be an unvisited neighbour of the new stack top.
Analysis of Option (d):
Start at : push .
To : unvisited neighbour of ; push .
To : unvisited neighbour of ; push .
To : unvisited neighbour of ; push .
From : all neighbours of are visited. Dead end: pop .
Stack top is now . Neighbours of include , which is unvisited.
However, option (d) jumps to vertex . Vertex is not adjacent to , and still has an unvisited neighbour (), prohibiting a backtrack past .
Conclusion: Sequence (d) is NOT a valid DFS order.
Problem 3: BFS on Directed Graphs with Unreachable Nodes:
Directed graph with vertices .
Directed edges:
Run BFS starting at with outgoing neighbours taken in alphabetical order.
Step-by-Step Execution:
Start at : mark visited, enqueue
[ A ].Dequeue : Output
A. Outgoing edges go to and . Both are unvisited; enqueue , then . Queue:[ B, C ].Dequeue : Output
B. has out-degree . No nodes enqueued. Queue:[ C ].Dequeue : Output
C. Outgoing edge goes to . is unvisited; enqueue . Queue:[ D ].Dequeue : Output
D. Outgoing edge goes to . is already visited; skip. Queue:[ ](empty).Traversal terminates.
Crucial Traps:
Unreachable Vertices: Vertex has out-degree (pointing to and ) but in-degree . No directed path exists from to . Consequently, is never visited.
Alphabetical Precedence: At vertex , neighbour precedes , ensuring appears before in the output.
Final BFS Output:
A, B, C, D.
Problem 4: DFS Visit Order versus Pop (Finish) Order:
Undirected 5-vertex graph with edges: .
Neighbour lists in ascending numerical order:
Execution Trace (Start = 1):
Step 1: Visit , push . Stack:
[ 1 ].Step 2: From , visit lowest unvisited neighbour , push . Stack:
[ 1, 2 ].Step 3: From , neighbour visited; visit , push . Stack:
[ 1, 2, 4 ].Step 4: From , neighbour visited; lowest unvisited neighbour is . Visit , push . Stack:
[ 1, 2, 4, 3 ].Step 5: From , neighbours and are both already visited. Dead end reached at . Pop 3 (first vertex to finish).
Step 6: Stack top is . Remaining unvisited neighbour is . Visit , push . Stack:
[ 1, 2, 4, 5 ].Step 7: From , neighbour is visited. Dead end. Pop 5.
Step 8: Stack top is . All neighbours visited. Pop 4.
Step 9: Stack top is . All neighbours visited. Pop 2.
Step 10: Stack top is . All neighbours visited. Pop 1.
Stack is empty.
Summary of Orders:
Visit Order (Push Order):
Finish Order (Pop Order):