MAT202: Introduction to Discrete Mathematics

Section 5.1 Modeling with Graphs

A graph is, simply, an object with vertices (or nodes), and edges (each of which connects two vertices). The power of graph theory lies in abstraction: given a problem with physical, structural, or time-related elements, modeling them as graphs allows us to focus our efforts at solving the problem on only the relevant details necessary. Consider the two examples below:

One day, you suddenly gain the power to walk through walls. Is there a way for you to walk through each wall of the building below (given its floor plan), such that you start and end in the same room (or the outside)? Assume you can visit any room as many times as you want, but cannot walk through each wall more than once.

For instance, the following path through the building does not pass through all walls (the walls in red are not used).

In the graph below, can you trace a path starting and ending at the same vertex that uses each edge exactly once? (Vertices can be repeated.)

You might be surprised to find out that answering Example 5.1.1 is equivalent to answering Example 5.1.2, in that a positive or negative answer to one implies the same answer for the other.

Here is how we can model the physical constraints of Example 5.1.1 as the graph in Example 5.1.2. Observe that to answer the question, we only need to determine which two rooms are incident to (or beside) each wall; let's assume the outside of the building is one big room as well. So we have six rooms, and we label them using the set \(V = \{u,v,w,x,y,z\}\) as follows:

Each wall can now be represented by a pair of rooms -- for example, the thick blue wall in the figure above can be represented as \((w,z)\text{,}\) while the north and west (red) walls of room \(y\) can both be represented as \((u,y)\text{.}\)

We can visually encode this information about each wall as an edge connecting the two rooms: we remove the floor plan, and draw all edges (the edges corresponding to the red and blue walls are highlighted in the graph).

Hence the question of whether or not it is possible to walk through all the walls of the building exactly once, is the same as determining if there is a way to walk along each edge of the graph obtained exactly once. For instance, here is the blue path shown in Example 5.1.1, as a trail along the graph (where red walls/edges are not used).

We will prove in a later example that it is impossible to construct a path through the building that satisfies the condition being asked. What is important now is that you understand how the problem was transformed into a question about a graph.

Read the next three exercises and think about how you can represent the given scenarios as graphs. We will come back to each of them in a later section.