Part I: The Beginning

In this part of the book, I introduce the fundamental concepts of graph theory that you will need to understand the rest of the textbook.

Chapter 1 is an overview of using graphs to solve problems. In order to ever use the graph theory you learn in this book, you will need to be able to pick the right graph with which to model a problem. In this chapter, you will get started on doing that. Many of the examples introduced here will be discussed later on in the textbook.

Chapter 2 covers isomorphic graphs, graph invariants, and subgraphs. It tells you when we consider two graphs to be the same, and which kind of properties of graphs are ones that graph theory concerns itself with. The idea of subgraphs will appear over and over, and the specific families of graphs introduced at the end of this chapter are important subgraphs to look out for.

Chapter 3 covers walks, paths, and cycles. If you use graphs to find how to get from one place to another, or more metaphorically how to get from one state of a system to another, then walks, paths, and cycles are exactly what you are looking for. This chapter also introduces connected graphs and connected components.

Chapter 4 covers degrees of vertices and their applications. It is only an introduction of the topic: the next part of the book is all about what we can do with vertex degrees. But the idea is too fundamental not to introduce in Part I: counting how many times an edge leaves a vertex is one of the simplest things we can do when faced with a graph, so it shows up over and over again later on in the book.

If writing mathematical proofs is new to you, consider reading this part of the book in parallel with the two chapters in the Appendix. These cover some proof techniques which are common in graph theory, especially proof by induction.