Skip to main content
🔗

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.

Floor plan of a house with five rooms.

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

Floor plan of a house with five rooms, with a path going through the rooms (but missing some walls).

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.)

Graph with six vertices and multiple edges.

🔗
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:

Floor plan of a house with five rooms, all rooms (and exterior) are labeled.

🔗
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), while the north and west (red) walls of room y can both be represented as (u,y).

🔗
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).

Graph with six labeled vertices corresponding to rooms and edges to walls.

🔗
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).

Path through rooms of the five-room house.
Corresponding trail through the graph.

🔗
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.

An about-to-be-married couple made the mistake of asking their 8 guests to indicate on their RSVPs who they would not like to sit with at the dinner reception. There will be two tables of four seats each (it is a really small venue).

Given the guestlist below, is there a way to seat the guests so that everyone is satisfied?

Guest Does not want to sit beside Guest Does not want to sit beside
Angela Donald Giuseppe Shinzo
Boris Emmanuel, Justin Justin
Donald Angela, Emmanuel, Justin Shinzo Donald
Emmanuel Boris Vladimir Emmanuel

You are working as a delivery person for a company selling medicinal herbs online. On April 20th, a particularly busy day, you have to make deliveries to Brampton, Burlington, Cambridge, and Guelph; the company has its distribution center in Mississauga, which is where you live as well. Given the table of distances below, can you determine the route that will take you from the distribution center in Mississauga, to each city exactly once, then back home, such that total distance traveled is minimized?

distance (km) Mississauga Brampton Burlington Cambridge Guelph
Mississauga 22 41 72 72
Brampton 22 60 75 65
Burlington 41 60 49 50
Cambridge 72 75 49 25
Guelph 72 65 50 25

Six graph theorists are at a conference. During a coffee break, each of them starts counting how many coauthors they have among the group (so 0 means that person has not written a paper with anyone in the group; 5 means that person has written a paper with everyone in the group). When they scribble the numbers down on a napkin, they get:

\begin{equation*} 3,2,2,2,1,1\text{.} \end{equation*}

Prove that this is impossible, so someone must have made a mistake counting.