Graph Theory

An Introduction to Proofs, Algorithms, and Applications

Karin R Saoub

• Publisher: Chapman and Hall/CRC
• Year: 2021
• Print ISBN:
  9780367743758
  9781138361409
• Edition: 1
• eBook ISBN:
  9780429779879
• Topic: Mathematics
• Subtopic: Programming Algorithms
• Index: Mathematics

Graph Theory: An Introduction to Proofs, Algorithms, and Applications

Graph theory is the study of interactions, conflicts, and connections. The relationship between collections of discrete objects can inform us about the overall network in which they reside, and graph theory can provide an avenue for analysis.

This text, for the first undergraduate course, will explore major topics in graph theory from both a theoretical and applied viewpoint. Topics will progress from understanding basic terminology, to addressing computational questions, and finally ending with broad theoretical results. Examples and exercises will guide the reader through this progression, with particular care in strengthening proof techniques and written mathematical explanations.

Current applications and exploratory exercises are provided to further the reader's mathematical reasoning and understanding of the relevance of graph theory to the modern world.

Features

The first chapter introduces graph terminology, mathematical modeling using graphs, and a review of proof techniques featured throughout the book

• The second chapter investigates three major route problems: eulerian circuits, hamiltonian cycles, and shortest paths.
• The third chapter focuses entirely on trees – terminology, applications, and theory.
• Four additional chapters focus around a major graph concept: connectivity, matching, coloring, and planarity. Each chapter brings in a modern application or approach.
• Hints and Solutions to selected exercises provided at the back of the book.

Author

Karin R. Saoub is an Associate Professor of Mathematics at Roanoke College in Salem, Virginia. She earned her PhD in mathematics from Arizona State University and BA from Wellesley College. Her research focuses on graph coloring and on-line algorithms applied to tolerance graphs. She is also the author of A Tour Through Graph Theory, published by CRC Press.

1

Graph Models, Terminology, and Proofs

This chapter will introduce you to some basic Graph Theory terminology and provide some motivation for the study of graphs. We begin by describing a specific type of graph called a tournament, and follow with a few sections outlining important terms and operations on graphs. This chapter also provides a basic review of proof techniques and concludes by revisiting tournaments.

1.1 Tournaments

Consider the following scenario:

The Roanoke Soccer League is planning their end-of-season tournament. Each of the five teams (Aardvarks, Bears, Cougars, Ducks, and Eagles) plays every other team exactly once and no ties are allowed. The tournament director must determine how many games are needed, how to schedule the games, and how to determine a winner once the tournament is completed.

The soccer tournament described above is often referred to as a round-robin tournament. While we can describe the tournament in words, or list the game outcomes in a table, it is often useful to provide a visual representation. One method, and the one we will continue to use throughout this book, is to model the information as a graph.

We will formally describe a graph next section, but for now think of a graph as a collection of dots (which we call vertices) on the page with lines (called edges) connecting the dots to indicate some relationship between them. In terms of the Roanoke Soccer League, we could represent each team as a vertex and put an edge between a pair of vertices if they have played each other. The following graphs G₁ and G₂ depict a possible way to run the first few games of the tournament and G₃ is the graph when all games of the tournament have been played (these are called complete graphs and will be discussed later).

Using the graphs above, we can help the tournament director answer at least one of the questions posed. The number of games needed is the same as the number of edges in the graph G₃ and without any complicated mathematics, we can easily count these and determine 10 total games are needed.

What about the other questions for the tournament director? We need to understand not just which teams played each other, but also the outcomes of these games. One way to do this is to add an arrow to each edge indicating a direction, what we will call a directed edge or arc. Once directions have been added to each of the edges, we now refer to the graph as a digraph, short for directed graph. The digraph shown below indicates that the Aardvarks won all their games, t...

Table of contents

• Cover
• Half Title
• Series Page
• Title Page
• Copyright Page
• Dedication
• Contents
• Preface
• 1 Graph Models, Terminology, and Proofs
• 2 Graph Routes
• 3 Trees
• 4 Connectivity and Flow
• 5 Matching and Factors
• 6 Graph Coloring
• 7 Planarity
• Appendix
• Selected Hints and Solutions
• Bibliography
• Image Credits
• Index