Q1.
a) State and prove the Euler’s formula for a connected planar graph G = (V, E). As well prove that if |V| > 2, then |E| ≤ 3|V| - 6
b) Prove that a simple graph is connected if and only if it consists of a spanning tree.
c) State the Kuratowski’s Theorem. For what purpose this theorem is employed? Show by an illustration, how this theorem is employed.
Give an illustration of a graph which you prove to be non-planar by using this theorem.
Q2.
a. What do you mean by the term Binary Search Tree (BST)? Construct a BST for the given sequence of numbers.
45, 32, 90, 34, 68, 72, 15, 24, 30, 66, 11, 50, 10
Traverse the BST so made in the Post-order.
b) Illustrate the difference between a spanning tree and a minimum spanning tree. Apply Prim’s algorithm on the given graph to find out minimum spanning tree.
