In a Directed Acyclic Graph (DAG), what is the minimum number of vertices with in-degree 0?
Every finite DAG must contain at least one vertex with in-degree 0 (a source).
If a graph G has an adjacency matrix that is symmetric ($A = A^{T}$), what type of graph is G?
In an undirected graph, an edge (u, v) implies edge (v, u), making A[u][v] = A[v][u] for all u, v. Thus the matrix is symmetric.
What is the time complexity to check whether a given undirected graph is bipartite using BFS?
Bipartiteness can be checked by 2-coloring the graph during BFS traversal in O(V + E) time.
What is the maximum number of connected components in a graph with V vertices?
When all V vertices are isolated (0 edges), the graph has V connected components.
What is the minimum number of connected components in a graph with V vertices (V >= 1)?
A non-empty graph has at least 1 connected component.