Cioaba S.M., Murty M.R. A First Course in Graph Theory and Combinatorics

New Delhi: Hindustan Book Agency, 2009. — 189 p.The concept of a graph is fundamental in mathematics since it conveniently encodes diverse relations and facilitates combinatorial analysis of many complicated counting problems. In this book, the authors have traced the origins of graph theory from its humble beginnings of recreational 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, Ontario, Canada between 2002 and 2008. The courses were aimed at students in their final year of their undergraduate program.Basic Notions of Graph Theory
The Königsberg Bridges Problem
What is a Graph?
Mathematical Induction and Graph Theory Proofs
Eulerian Graphs
Bipartite Graphs
ExercisesRecurrence Relations
Binomial Coefficients
Derangements
Involutions
Fibonacci Numbers
Catalan Numbers
Bell Numbers
ExercisesThe Principle of Inclusion and Exclusion
The Main Theorem
Derangements Revisited
Counting Surjective Maps
Stirling Numbers of the First Kind
Stirling Numbers of the Second Kind
ExercisesMatrices and Graphs
Adjacency and Incidence Matrices
Graph Isomorphism
Bipartite Graphs and Matrices
Diameter and Eigenvalues
ExercisesTrees
Forests, Trees and Leaves
Counting Labeled Trees
Spanning Subgraphs
Minimllm Spanning Trees and Kruskal's Algorithm
ExercisesMobius Inversion and Graph Colouring
Posets and Mobius Functions
Lattices
The Classical Mobius Function
The Lattice of Partitions
Colouring Graphs
Colouring Trees and Cycles
Sharper Bounds for the Chromatic Number
Sudoku Puzzles and Chromatic Polynomials
ExercisesEnumeration under Group Action
The Orbit-Stabilizer Formula
Burnside's Lemma
Plya Theory
ExercisesMatching Theory
The Marriage Theorem
Systems of Distinct Representatives
Systems of Common Representatives
Doubly Stochastic Matrices
Weighted Bipartite Matching
Matchings in General Graphs
Connectivity
ExercisesBlock Designs
Gaussian Binomial Coefficients
Introduction to Designs
Incidence Matrices
Examples of Designs
Proof of the Bruck-Ryser-Chowla Theorem
Codes and Designs
ExercisesPlanar Graphs
Euler's Formula
The Five Colour Theorem
Colouring Maps on Surfaces of Higher Genus
ExercisesEdges and Cycles
Edge Colourings
Hamiltonian Cycles
Ramsey Theory
ExercisesRegular Graphs
Eigenvalues of Regular Graphs
Diameter of Regular Graphs
Ramanujan Graphs
Basic Facts about Groups and Characters
Cayley Graphs
Expanders
Counting Paths in Regular Graphs
The Ihara Zeta Function of a Graph
ExercisesHints