What is the maximum number of edges in a simple undirected graph with V vertices that is NOT connected?
To maximize edges without connecting the graph, isolate 1 vertex and form a complete graph $K_{V-1}$ on the remaining V - 1 vertices. Edges = (V - 1)(V - 2) / 2.
What is the minimum number of edges in a connected undirected graph with V vertices?
A minimally connected undirected graph with V vertices is a Tree, which contains exactly V - 1 edges.
In a strongly connected directed graph $G = (V$, E), for every pair of vertices u and v:
A directed graph is strongly connected if every vertex is reachable from every other vertex via a directed path.
Kosaraju's algorithm finds all Strongly Connected Components (SCCs) of a directed graph in what time complexity?
Kosaraju's algorithm performs two DFS traversals (one on G and one on reversed graph $G^{T})$, running in O(V + E) time.
Tarjan's algorithm computes Strongly Connected Components (SCCs) using how many DFS passes?
Tarjan's algorithm finds all SCCs in a single DFS pass using discovery times and low-link values with a stack.