A First Course in Graph Theory and Combinatorics

The concept of a graph is fundamental in mathematics since it con- veniently encodes diverse relations and facilitates combinatorial anal- ysis of many complicated counting problems. In this book, we have traced the origins of graph theory from its humble beginnings of recre- ational mathematics to its modern setting for modeling communication networks as is evidenced by the world wide web graph used by many internet search engines. This book is an introduction to graph theory and combinatorial analysis. It is based on courses given by the second author at Queen's University at Kingston, Canada between 2002 and 2008. The courses were aimed at students in their final year of their undergraduate pro- gram. As such, we believe this text is very suitable for a first course on this topic. Graph theory and combinatorics interact well with other branches of mathematics like number theory, algebraic topology, algebraic geom- etry and representation theory as well as other sciences. For instance, Ramanujan graphs and expander graphs have gained prominence with applications to the construction of optimal communication networks. Thus, we have included a chapter on this important emerging theme at the end of the book.