Section 1.1 Motivation
Why should we study graph theory? For any mathematical topic, there are always two possible answers to such a question. First, because it is interesting. Second, because it is useful. (Some might dispute the order in which we have placed these reasons, but they are wrong.)
Our hope is that our presentation throughout this text will convince you that graphs are interesting. We will occasionally also try to point out ways in which they are useful. Their utility can be in service to either a “real world” or “practical” application, or to other areas of mathematics. As often happens, all these blend together; practical applications motivate mathematicians to study interesting properties abstractly, which in turn help us understand mathematics more generally, providing usefulness to the pure subject.
Oh, also graphs can be used to solve puzzles. We leave it to the reader to decide to what category of utility this belongs.
The original graph theory puzzle is the Bridges of Königsberg. As the story goes, Euler was asked whether it was possible to traverse the 7 bridges of the town, arranged as shown below, each exactly once.
This is a rather well known puzzle, which will motivate us to develop a theory of graph traversals. For now though, let's consider a few puzzles that might not seem to immediately relate to graphs. For each of these, we should think about what mathematical objects would be useful to model the problem.
Puzzle 1.
On the table rest 8 dominoes, as shown below. If you were to line them up in a single row, so that any two sides touching had matching numbers, what would the sum of the two end numbers be?
We will give the solution as well as a description of how graphs can be used to represent and solve the problem.
Notice that the value 1 only appears on one tile, and so 1 must be on one end of your row. This highlights an important property: Any tile in the middle of your row must be paired with another tile that has the same number. All the values except 1 and 4 show up on an even number of tiles, so all of those tiles could be on the interior of your row. However, 4 could only be in the inside of the row once (using 2 of the tiles), and so the 4 would have to be at the other end of your row. Therefore, your row would have to end with the values 1 and 4, making their sum 5.
How does this relate to graph theory? One of our goals is to identify when graphs are useful, but also when they are not. We could create a graph to represent many of the relationships that are important to this problem. For example, we could create a graph where each vertex is a tile and place edges between tiles that could be connected. Just because we can does not mean that we should. If we connected the tiles in this way we would see 1 and 4 connected to at least one other tile and the fact that there was an odd number of tiles with those values would be obscured. In this case, a solution that did not include graphs was much more useful for our purposes. Before we jump to using a graph to solve a problem we should ask: Is this a problem where a graph will demonstrate the relationships I am interested in demonstrating?
Puzzle 2.
Professor Nefario has invited 25 unsuspecting discrete math students to his estate for an evening of escape room fun. Some of these students are already friends, but no student is friends with more than 3 other students. The Professor wants to ensure that no friends are sent to the same escape room. Can he be sure that four escape rooms will be enough?
Yes, Professor Nefario can be sure that four escape rooms is enough. Here is how. Professor Nefario can assign the first 4 students each to a different room. Profesor Nefario knows that student 5 has no more than 3 friends so their must be a room that has no friends of student 5. Professor Nefario can assign student 5 to that room. If there is more than one room that has no friends of student 5 then Professor Nefario can choose any of those rooms. As he progresses through the students Professor Nefario can repeat this process. Each student has no more than 3 friends so there must be a room that has no friends of that student, therefore there is a room that student can be assigned.
So how does this related to graph theory? Suppose you have a graph with 25 vertices and no vertice of degree greater than 3. Is it possible to color the graph with 4 colors?
The answer is yes and follows the same logic Professor Nefario used to assign students to escape rooms. Pick 4 vertices and assign them different colors. Pick an uncolored vertex. That vertex connects to no more than three vertices so there is at least one available color. Color the vertex one of the available colors. Repeat until each vertex has been colored.
Puzzle 3.
Is it possible that among the 25 students, everyone has exactly three friends?
No, it is not possible. Consider for one person to have three friends, then there are at least three friendships. We can consider each person as a vertex and each friendship as an edge. In graph theory we can ask can you create a graph with 25 vertices, with each vertex with degree 3. Notice that for any two people that are friends, they each claim the friendship, i.e. if person A is friends with person B, then person B is also friends with person A. Thus, there is no way for 25 friends to each have 3 friendships.
Puzzle 4.
Take a regular deck of 52 cards, shuffle well, and deal the cards into 13 piles. Will it always be possible to select one card from each pile so that the 13 cards you select all have different values (ace, 2, 3, etc.)?
What can we learn from the puzzles above?