Graph Theory is a delightful playground for the exploration of proof techniques in discrete mathematics, and its results have applications in many areasof computing, social, and natural sciences. How can we lay cable at minimum cost to make every telephone reachable from every other? What is the fastest route from the national capital to each state capital? How can n jobs be filled by n people with maximum total utility? What is the maximum flow per unit time from source to sink in a network of pipes? How many layers does a computer chip needso that wires in the same layer don’t cross? How can the season of a sports league be scheduled into the minimum number of weeks? In what order should a travelling salesman visit cities to minimum number of weeks? Can we colour the regions of every map using four colours so that neighbouring regions receive different colours? These and many other practical problems involve graph theory (D. B. West, 2002 page1).