How many spanning trees exist for a complete graph $K_{4}$ with 4 labeled vertices?
$Using Cayley's formula n^{n-2}: 4^{4-2} = 4^2 = 16 spanning trees.$
Which algorithm can solve the All-Pairs Shortest Path problem faster than Floyd-Warshall on sparse weighted graphs with non-negative edges?
Running Dijkstra from each vertex with a binary min-heap takes O(V(E+V) log V). For sparse graphs where $E = O(V)$, this is O($V^2$ log V), which is asymptotically faster than Floyd-Warshall's O($V^3)$.
Johnson's Algorithm solves All-Pairs Shortest Paths on sparse graphs with possible negative edges but no negative-weight cycles. What is its time complexity using Fibonacci heaps?
Johnson's algorithm runs Bellman-Ford once and Dijkstra from every vertex after reweighting. With Fibonacci heaps, the total time is O(VE + $V^2$ log V).
What is the maximum number of edges in a bipartite graph $K_{3,4}$?
$A complete bipartite graph K_{m,n} has m * n edges = 3 * 4 = 12 edges.$
Which of the following statement is TRUE for a tree with V vertices?
By definition, a tree is an acyclic connected undirected graph.