A simple undirected graph G has 12 vertices and each vertex has degree 4. How many edges does graph G contain?
According to Handshaking Lemma, sum of degrees of all vertices = 2 * |E|. Here 12 * 4 = 48. So 2 * |E| = 48 => |E| = 24.
What is the total number of edges in a complete undirected graph $K_{n}$ with 10 vertices?
Number of edges in a complete graph $K_{n} = n \cdot (n - 1)/2 = 10 \cdot 9 / 2 = 45$.
What is the memory space complexity required to represent a graph with V vertices and E edges using an Adjacency Matrix?
An adjacency matrix is a V x V 2D array, which always occupies O($V^2)$ memory space regardless of the number of edges E.
What is the space complexity to represent a directed graph with V vertices and E edges using an Adjacency List?
An adjacency list contains V array heads and a total of E list nodes for a directed graph, giving space complexity O(V + E).
In an undirected graph represented by an Adjacency Matrix A, how is the degree of vertex i calculated?
In an undirected graph without self-loops, A[i][j] = 1 if an edge exists between i and j. The degree of vertex i equals the sum of all elements in row i (or column i).