Which edge classification in DFS indicates a cycle in an UNDIRECTED graph?
In an undirected graph DFS, reaching an already visited vertex that is NOT the immediate parent indicates a cycle (back edge).
In a simple graph with n vertices, what is the maximum degree any single vertex can have?
Without self-loops or parallel edges, a vertex can connect to at most n - 1 other vertices.
What is the time complexity to compute the transpose $G^{T}$ of a directed graph represented by an Adjacency List?
Reversing all edge directions in an adjacency list requires visiting each vertex and edge once, taking O(V + E) time.
In a weighted graph where edge weights can be negative but NO negative cycles exist, which algorithm finds single-source shortest paths?
Bellman-Ford correctly handles negative edge weights as long as no negative cycles exist.
What is the total number of edges in a wheel graph $W_{n}$ with n vertices (n >= 4)?
A wheel graph $W_{n}$ consists of a rim cycle with n - 1 vertices (n - 1 edges) and 1 central hub connected to all n - 1 vertices (n - 1 edges). Total = 2(n - 1) edges.