In a regular graph, all the vertices will be of the same degree. Total degrees of all the vertices is nd. Each edge will be increasing the total degree by 2. So, totally nd/2 edges.
18:
Let G be a non-planar graph with the minimum possible number of edges. Then G has
Any non-planar graph has K_{5} or K_{3,3} as a subgraph. Both these subgraphs are non-planar. K_{5} has 5 vertices and 10 edges. K_{3,3 }has 6 vertices and 9 edges. Since we are interested in the non-planar with the fewest number of edges, option (B) is the correct choice.
19:
Which of the following graphs has an Eulerian circuit?
In a k-regular graph, all the vertices are of degree k. If all the vertices in a graph have even degree, there exists an Eulerian circuit (or cycle).
20:
In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity, by