This book serves as an introduction to graph theory and its applications. It is intended for a senior undergraduate course in graph theory but is also appropriate for beginning graduate students in science or engineering. The book presents a rigorous (proof-based) introduction to graph theory while also discussing applications of the results for solving real-world problems of interest. The book is divided into four parts. Part 1 covers the combinatorial aspects of graph theory including a discussion of common vocabulary, a discussion of vertex and edge cuts, Eulerian tours, Hamiltonian paths and a characterization of trees. This leads to Part 2, which discusses common combinatorial optimization problems. Spanning trees, shortest path problems and matroids are all discussed, as are maximum flow problems. Part 2 ends with a discussion of graph coloring and a proof of the NP-completeness of the coloring problem. Part 3 introduces the reader to algebraic graph theory, and focuses on Markov chains, centrality computation (e.g., eigenvector centrality and page rank), as well as spectral graph clustering and the graph Laplacian. Part 4 contains additional material on linear programming, which is used to provide an alternative analysis of the maximum flow problem. Two appendices containing prerequisite material on linear algebra and probability theory are also provided.

Contents:

• 
  

  Introduction to Graphs:

  
  
  
  
  • Introduction to Graph Theory
  
  
  • Degree Sequences and Subgraphs
  
  
  • Walks, Cycles, Cuts, and Centrality
  
  
  • Bipartite, Acyclic, and Eulerian Graphs
  
  
  
  


• 
  

  Optimization in Graphs and NP-Completeness:

  
  
  
  
  • Trees, Algorithms, and Matroids
  
  
  • An Introduction to Network Flows and Combinatorial Optimization
  
  
  • Coloring
  
  
  
  


• 
  

  Some Algebraic Graph Theory:

  
  
  
  
  • Algebraic Graph Theory with Abstract Algebra
  
  
  • Algebraic Graph Theory with Linear Algebra
  
  
  • Applications of Algebraic Graph Theory
  
  
  
  


• 
  

  Linear Programming and Graph Theory:

  
  
  
  
  • A Brief Introduction to Linear Programming
  
  
  • Max Flow/Min Cut with Linear Programming
  
  
  
  


• 
  

  Appendices:

  
  
  
  
  • Fields, Vector Spaces, and Matrices
  
  
  • A Brief Introduction to Probability Theory
  
  
  
  

Readership: Advanced Undergraduate Students or Beginning Graduate Students in Mathematics (those who have taken a first course in proofs). Graduate Students in STEM who want a rigorous text on graph theory that also focuses on applications. This could be used as a secondary text in a physics course on Network Science, or potentially in a rigorous course in theoretical computer science or operations research with graph theory.

Key Features:

• This book is unique among graph theory books for undergraduates in its coverage of classical graph theory results, graph algorithms (i.e., combinatorial optimization) with a proof of the NP-completeness of k-colorability, and a thorough discussion of algebraic graph theory that includes modern uses of this theory, such as page rank and spectral clustering


• Another unique aspect of this text is the double coverage of the max flow/min cut theorem. The text covers the theorem using classical arguments but also provides a secondary introduction using linear programming and the Karush-Kuhn-Tucker conditions, allowing courses in operations research to connect classical graph theory with other courses in optimization


• While the book is rigorous, presented in a theorem-proof style, there are applications contained in almost every chapter either through examples or discussion. Each chapter ends with a notes section that discusses historical context or additional applications