Introduction to Graph Theory Solutions Manual Koh Khee Meng National University of Singapore, Singapore Dong Fengming Tay Eng Guan Nanyang Technological University, Singapore
Introduction to Graph Theory Solutions Manual (Koh Khee Meng, Dong Fengming, Tay Eng Guan)

Preface
Discrete Mathematics is a branch of mathematics dealing with finite or countable processes and elements. Graph theory is an area of Discrete Mathematics which studies configurations (called graphs) consisting of a set of nodes (called vertices) interconnecting by lines (called edges). Fromd humble beginnings and almost recreational type problems, Graph Theory has found its calling in the modern world of complex systems and especially of the computer. Graph Theory and its applications can be found not only in other branches of mathematics, but also in scientific disciplines such as engineering, computer science, operational research, management sciences and the life sciences. Since computers require discrete formulation of problems, Graph Theory has become an essential and powerful tool for engineers and applied scientists, in particular, in the area of designing and analyzing algorithms for various problems which range from designing the itineraries for a shipping company to sequencing the human genome in life sciences.
Graph Theory shows its versatility in the most surprising of areas. Re-
cently, the connectivity of the World Wide Web and the number of links needed to move from one webpage to another has been remarkably mod-
eled with graphs, thus opening the real world internet connectivity to more rigorous studies. These studies form part of research in the phenomena of the property of a ' small world' even in huge systems such as the afore-
mentioned internet and global human relationships (in the so-called ' Six Degrees of Separation').
This book is intended as a companion to our earlier book Introductiond to Graph Theory (World Scientific, 2006). Here, we present worked solutions to all the exercise problems in the earlier book. Such a collection of solutions is perhaps the first of its kind. We believe that the student who has worked on the problems himself will find the solutions presented here useful as a check and as a model for rigorous mathematical writing. Ford ease of reference, each chapter begins with a recapitulation of some of the important concepts and/or formulae from the earlier book.