Section 3.1 Modeling with Graphs

After an introductory puzzle, we define a graph, introduce some vocabulary used to describe graphs, and practice modeling situations using a graph.

Subsection 3.1.A Crossing Bridges

We begin with a puzzle.

Activity 3.1.A Bridges Puzzle.

A small city sits on the north and south shores of a river and on two islands on the river, a small island and a big island, as shown in Figure 3.1.2. Residents enjoy walking around the city each day, crossing the bridges that connect the islands to each other and to the north and south shore. To keep their walks interesting, they never cross the same bridge twice in a day.

Figure 3.1.2. A small city connected by bridges.

Show that it is possible to start a daily walk on the small island and cross every bridge (exactly once each). You end up somewhere other than the small island (with no way back to where you started). Where do you end? Any thoughts on why you end there?
Why is it impossible to start a daily walk on the small island, cross every bridge (exactly once each), and end on the small island? Hint: There are three bridges connected to the small island. The first bridge you cross takes you off the small island. At some point you cross a second bridge connected to the small island. Where are you then? Where are you after crossing the third bridge connected to the small island?
What happens if you start a daily walk somewhere else (not on small island) and cross every bridge connected to small island (exactly once each)? Hint: Whichever of the bridges connected to small island that you cross first takes you onto small island. Where are you after the next bridge you cross? At some point you cross the third bridge connected to the small island. Where are you then?
Explain why it is impossible to start a daily walk somewhere other than small island, cross every bridge (exactly once each), and end where you started.
Look at the number of bridges connected to each piece of land. What about that number matters in trying to find a daily walk that crosses each bridge (exactly once each)?

Let’s examine the key elements of Activity 3.1.A. In the puzzle, it did not matter where the north shore, the south shore, the small island, and the big island were geographically. We did not care how long the bridges were or what angle they made with the shore or island. It also did not matter that the small island is smaller than the big island. We did not even care which pieces of land were islands and which were the shores of the river. All that mattered was which pieces of land had a bridge, or two, between them.

Subsection 3.1.B The Definition of a Graph

In Activity 3.1.A, the essential information we needed to know about the city was the set of objects (the pieces of land) and the connections between them (the bridges). Any set of objects with connections between pairs of objects is a graph.

Definition 3.1.3 Graph.

A vertex (or node) is an object. For example, a vertex could be a piece of land in the city from Activity 3.1.A or perhaps a student at the university. The plural of “vertex” is “vertices” and so we refer to one vertex, two vertices, three vertices, and so on.
An edge is a set of two vertices. For example, if \(A\) and \(B\) are distinct vertices in a graph, then \(\{A,B\}\) is an example of a possible edge. When we model a situation using a graph, each edge represents a connection between two objects. For example, in the Bridges Puzzle Activity 3.1.A, we might want an edge between two vertices to indicate that those two pieces of land are connected by a bridge.
¹

We are ignoring, for the moment, that there are two bridges between the big island and the north shore. Technically we need a slightly more general definition of an edge and what we get is a multigraph, not a simple graph.
As another example, in a graph where each vertex is a student at the university, we might want an edge between two vertices to indicate that those two students have a class together this semester.
Two vertices are adjacent (or neighbors) if they are connected by an edge. That is, if \(A\) and \(B\) are distinct vertices and \(\{A,B\}\) is an edge, then the vertices \(A\) and \(B\) are adjacent. We also say that \(A\) is adjacent to \(B\) or that \(B\) is adjacent to \(A\text{.}\) So, for example, if Camilla and Quang are both in discrete mathematics class this semester, then Camilla is adjacent to Quang (and vice versa) in the student graph.
A (simple) graph (or network) is a pair of sets: a vertex set of vertices and a edge set of edges where the elements of each edge are in the vertex set. For example, we might have the graph \(G\) with the vertex set \(\{1,2,3,4\}\) and the edge set

\begin{equation*} \{\{1,2\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}\}\text{.} \end{equation*}
A graph drawing of a graph has a point for each vertex and a line (or curve) for each edge connecting its two vertices. In this textbook, we draw each vertex as a small, open circle instead of a point. The placement of the vertices and edges is at our convenience– none of the geometry such as position, length, or angle matters. For example, Figure 3.1.4 shows four different drawings of the graph \(G\) from (d).

Figure 3.1.4. Four different drawings of the graph \(G\text{.}\)

The city in the Bridges Puzzle can be modeled with a multigraph which is a graph where multiple edges are allowed between the same pair of vertices.

Example 3.1.5 Bridges as a graph.

Draw a multigraph representing the city in the Bridges Puzzle Activity 3.1.A.

Solution.

The graph is drawn in Figure 3.1.6. The graph has four vertices, one for each piece of land. We have labeled them in the graph drawing for convenience. For each bridge in Figure 3.1.2 between two pieces of land, we draw an edge connecting the corresponding vertices in the graph. For example, there is a bridge connecting the small island and the big island, so in our graph drawing we have an edge between the vertices labeled small island and big island. There is no bridge connecting the north shore and the south shore, so in our graph drawing we do not have an edge between the vertices labeled north shore and south shore.

Figure 3.1.6. A multigraph representing the city in the Bridges Puzzle.

Let’s look at an another example of a graph model.

Example 3.1.7 Classmates graph.

Abdi, Bhavika, Cara, Drew, Elle, and Filipe are all new transfer students. This semester, Abdi, Bhavika, and Cara are in a discrete mathematics class together; Bhavika, Cara, and Drew are in an algorithms class together; and Abdi and Elle are in chemistry class together. These students do not have other classes in common.

We can model these relationships with a graph. The vertex set \(\{A,B,C,D,E,F\}\) has a vertex for each student corresponding to the first letter of their name. Let’s say two vertices are connected by an edge if those two students are taking the same class. If students have any number of classes together, we will just draw a single edge. This graph might be useful for visualizing who knows each other.

Explain why \(\{A,C\}\) is an edge but \(\{B,E\}\) is not.
Solution.

Abdi and Cara are in the discrete mathematics class, so \(\{A,C\}\) is an edge. All common classes are listed, and there is no class that Bhavika and Elle are taking, so \(\{B,E\}\) is not an edge.
How many edges are in the graph?
Solution.

First, since Abdi, Bhavika, and Cara are in a discrete mathematics class together, we have three edges \(\{A,B\}\text{,}\) \(\{A,C\}\text{,}\) and \(\{B,C\}\text{.}\) Next, since Bhavika, Cara, and Drew are in an algorithms class, we have two more edges \(\{B,D\}\) and \(\{C,D\}\text{.}\) We already knew that \(\{B,C\}\) was an edge, so we do not draw that edge again. Lastly, since Abdi and Elle are in the same chemistry class, we have one more edge: \(\{A,E\}\text{.}\) There are a total of six edges.
Draw the graph.
Solution.

Figure 3.1.8 shows one possible drawing of the graph. In this drawing, we chose to draw the vertices in a circle. The lines representing the edges \(\{A,C\}\) and \(\{B,D\}\) happen to cross, which is acceptable, but note that the point where those two edges cross is not a vertex. That is the sort of potential misunderstanding that we avoid by drawing our vertices as small circles instead of actual points.

Figure 3.1.8. One drawing of the classmates graph.

It is useful to have a name for the number of edges that include a particular vertex.

Definition 3.1.9 Degree of vertex.

The degree of a vertex \(v\) in a graph \(G\text{,}\) denoted \(\fn{deg}_G(v)\) or just \(\fn{deg}(v)\text{,}\) is the number of edges of \(G\) that contain the vertex \(v\text{.}\) For example, in the graph \(G\) from Definition 3.1.3 (d) with vertex set \(\{1,2,3,4\}\) and edge set

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

vertex 1 has degree two because 1 is an element of two edges: \(\{1,2\}\) and \(\{1,4\}\text{.}\) Vertex 2 has degree three because 2 is an element of three edges: \(\{1,2\}\text{,}\) \(\{2,3\}\text{,}\) and \(\{2,4\}\text{.}\) In the drawings in Figure 3.1.4, we see two edges to vertex 1 and three edges to vertex 2.
Equivalently, the degree of a vertex is the number of neighbors of the vertex. For example, in the graph \(G\) from Definition 3.1.3 (d), vertex 1 has degree two because it has two neighbors, 2 and 4. Similarly, vertex 2 has degree three because it has three neighbors, 1, 3, and 4.
An isolated vertex is a vertex with degree zero. For example, \(F\) is an isolated vertex in the classmates graph in Example 3.1.7, because Felipe was not a classmate of anyone else in the group of new transfer students. In Figure 3.1.8 there are no edges to the vertex \(F\text{.}\)
A end vertex (or leaf or pendant) is a vertex with degree 1. For example, in the classmates graph from Example 3.1.7, \(E\) is an end vertex because Elle was only in a class with Abdi. In Figure 3.1.8 we see one edge to the vertex \(E\text{.}\)

Practice modeling with graphs.

Activity 3.1.B Cube graph.

Consider a graph \(Q\) whose vertices are the bit strings of length three and where two vertices are connected by an edge if they differ in exactly one bit.

We could equivalently say that the bit strings have Hamming distance one, as defined in Section 2.4 Exercise 5.

For example, the vertices \(\bs{010}\) and \(\bs{011}\) which are connected by an edge because they differ in only their third bit, but the vertex \(\bs{010}\) is not connected by an edge to the vertex \(\bs{111}\) because they differ in both the first and third bit.

How many vertices does \(Q\) have? Hint: There should be one vertex for each bit string of length three.
List the vertices of the graph \(Q\text{.}\)
Explain why the vertices labeled \(\bs{010}\) and \(\bs{011}\) are connected by an edge.
List the vertices adjacent to the vertex labeled \(\bs{010}\text{.}\) These are the neighbors of the vertex labeled \(\bs{010}\text{.}\)
What is the degree of the vertex \(\bs{010}\text{?}\)
Explain why every vertex in \(Q\) has the same degree.
Draw the graph \(Q\text{.}\)
Count the number of edges in \(Q\text{.}\)
The graph \(Q\) is an example of a cube graph. Can you redraw \(Q\) to see where that name comes from?

Subsection 3.1.C Graph Complements

When we first introduced graphs in Subsection 3.1.B, we explained that in a graph, \(G\text{,}\) an edge connecting two vertices, \(v\) and \(w\text{,}\) indicates that the two objects, \(v\) and \(w\text{,}\) are related in some way. For example, in Example 3.1.7, the objects were a group of new transfer students and an edge between two vertices indicated that the two students were in a class together this semester. That graph is helpful if we want to visualize who knows each other. Suppose instead that we wanted to set up one-on-one meetings for new transfer students who do not yet know each other. We might want to draw a new graph where the objects are the same group of new transfer students, but now an edge between two vertices indicates that the two students are not in a class together this semester. This new graph, \(\overline{G}\text{,}\) has the same vertices as \(G\text{,}\) but now an edge connecting two vertices, \(v\) and \(w\text{,}\) indicates that the two objects, \(v\) and \(w\) are related in the opposite way.

We formally define the graph complement.

Definition 3.1.11 Graph complement.

For a graph, \(G\text{,}\) the (graph) complement, \(\overline{G}\text{,}\) has the same set of vertices but opposite edges in the sense that \(\{v,w\}\) is an edge of \(\overline{G}\) exactly when \(\{v,w\}\) is not an edge in \(G\text{.}\) Equivalently, \(v\) and \(w\) are adjacent in \(\overline{G}\) exactly when \(v\) and \(w\) are not adjacent in \(G\text{.}\)

Let’s draw the complement of the classmates graph.

Example 3.1.12 Complement of the classmates graph.

Draw the complement of the classmates graph in Figure 3.1.8.

Solution.

We draw the complement in Figure 3.1.13.

Figure 3.1.13. The complement of the classmates graph.

For example, \(A\) and \(D\) are not adjacent vertices in the classmates graph because Abdi and Drew are not in any of the same classes this semester. Therefore, \(A\) and \(D\) are adjacent vertices in the complement of the classmates graph. As another example, \(B\) and \(C\) are adjacent vertices in the classmates graph because Bhavika and Cara are in the algorithms class together this semester. Therefore, \(B\) and \(C\) are not adjacent vertices in the complement of the classmates graph.

Your turn to work with complements.

Activity 3.1.C Graph complement.

Consider the graph \(G\) drawn in Figure 3.1.15.

How many vertices and edges does the graph \(G\) have?
List each vertex of \(G\) and its degree.
Draw the graph complement \(\overline{G}\text{.}\)
How many vertices and how many edges does the graph \(\overline{G}\) have?
List each vertex of \(\overline{G}\) and its degree.
What is the relationship between the degree of a vertex in \(G\) and the degree of the same vertex in \(\overline{G}\text{?}\)
What is the relationship between the number of edges in \(G\) and the number of edges in \(\overline{G}\text{?}\)

Let’s work through Activity 3.1.C (f).

Example 3.1.16 Degree of a vertex in the complement.

In the graph \(G\) drawn in Figure 3.1.15, what is the relationship between the degree of a vertex in the graph \(G\) and the degree of that same vertex in the complement \(\overline{G}\text{?}\)

Solution.

As an example, the vertex \(v\) is adjacent to \(w\text{,}\) \(x\text{,}\) and \(z\) in \(G\) and \(v\) is adjacent to \(y\) in \(\overline{G}\text{.}\) Thus, \(\fn{deg}_G(v) = 3\) and \(\fn{deg}_{\overline{G}}(v) = 1\text{.}\) As another example, the vertex \(z\) is adjacent to \(v\) and \(y\) in \(G\) and \(z\) is adjacent to \(w\) and \(x\) in \(\overline{G}\text{.}\) Thus, \(\fn{deg}_G(z) = 2\) and \(\fn{deg}_{\overline{G}}(z) = 2\text{.}\) In general, if \(x\) is any vertex in \(G\text{,}\) then

\begin{equation*} \fn{deg}_G(x) +\fn{deg}_{\overline{G}}(x) = 4\text{.} \end{equation*}

This equation holds for any vertex, \(x\text{,}\) because there are four other vertices in \(G\text{.}\) Some of those four vertices are adjacent to \(x\) in \(G\text{.}\) The remainder of those four vertices must be adjacent to \(x\) in \(\overline{G}\text{.}\) So, each of those other four vertices counts once in either \(\fn{deg}_G(x)\) or \(\fn{deg}_{\overline{G}}(x)\text{.}\)

Subsection 3.1.D Exercises

Subsubsection Exercises for 3.1.A Crossing Bridges

1. Practice.

Could we build a new bridge in the city described in Activity 3.1.A so that it would be possible to take a daily walk crossing every bridge (exactly once each) and ending where you started? Explain.

Check.

Hint: Yes, say where and list a daily walk that crosses every bridge (exactly once each) and ends where you start.

2. Understand.

In the city described in Activity 3.1.A, we would like to start our daily walk on the big island and cross every bridge (exactly once each).

Suppose that there exists such a walk. Explain why we would end on the small island.
Again, suppose that there exists such a walk. Explain why it would end on the north shore.

Since we cannot end in two different places, we have a contradition (false statement). Therefore, our supposition that there exists such a walk is also false, which means that it is impossible.

We discuss this type of proof by contradiction in Section 5.1.

3. Explore.

Suppose that we have a completely new city on a river with islands and bridges. As in Activity 3.1.A, residents enjoy walking around the city each day, crossing bridges, and to keep their walks interesting, they never cross the same bridge twice in a day.

Conjecture how you could tell if it is possible to take a daily walk that crosses every bridge (exactly once) and ends where you started. Hint: your answer should involve quantities that we can quickly calculate from a drawing of the city.
Now, conjecture how you could tell if it is possible to take a daily walk that crosses every bridge (exactly once) but ends at a location that is different from where you started. Hint: your answer should involve quantities that we can quickly calculate from a drawing of the city.

Subsubsection Exercises for 3.1.B The Definition of a Graph

4. Practice.

Consider a graph \(G\) with vertex set

\begin{equation*} \{u, v, w, x, y\} \end{equation*}

and edges \(\{u,v\}\text{,}\) \(\{u,w\}\text{,}\) \(\{u,x\}\text{,}\) \(\{v,x\}\text{,}\) \(\{w,x\}\text{,}\) \(\{x,y\}\text{.}\)

Count the number of vertices in \(G\text{.}\)
Count the number of edges in \(G\text{.}\)
List the neighbors of the vertex \(x\text{.}\) Hint: The vertex \(x\) might occur as the first or second element of the edge.
Calculate the degree of the vertex \(x\text{.}\)
Draw the graph \(G\) and check your answers.
Is there any end vertex in \(G\text{?}\) Explain.

Check.

Five
Six
Hint: The vertex \(u\) is one neighbor and there are three others.
Hint: The degree of \(x\) is equal to the number of neighbors.
Hint: Check that you have five vertices and six edges.
Yes, there is one end vertex.

5. Understand.

Consider the map of midwest states in Figure 3.1.22.

Draw a graph with a vertex for each state and an edge between two vertices if their corresponding states share a length of common border (more than a point).

Figure 3.1.22. Map of midwest states.
How many vertices does the graph have?
List the neighbors of Minnesota (MN).
Find the degree of each state.
Which two states have the highest degree? Explain.
How many edges does the graph have?

Check.

See Figure 3.1.22 in Section 3.2.
13
Hint: MN has four neighbors.
ND:2, SD: 4, NE: 4, …, IL: 3
Iowa (IA) and Missouri (MO)
24

6. Understand.

Given a set of words, we can construct a word graph whose vertices are the given words where two words are connected by an edge if one word can be changed to the other by making exactly one of the following changes.

Reorder.
Keep the same letters, but change the order.
Replace.
Keep the letters in the same order, but replace one letter with a different letter.

Note that each change is reversible, so it makes sense to say that two words are connected by an edge.

Draw the word graph for the set \(\{ACT, APT, CAT, HAT, HOT, HIT, PAT, PIT, PUN\}\text{.}\)
How many vertices does your graph have?
What is the degree of the vertex CAT?
Are any of the vertices in your graph an end vertex?
Are any of the vertices in your graph an isolated vertex?
How many edges does your graph have?

Check.

See the graph in Figure 3.1.24.

Figure 3.1.24. Word graph
Hint: count the number of words.
Hint: the neighbors of CAT are ACT, HAT, and PAT.
No
Yes
11

7. Understand.

In front of you are two coins laying on the table: a quarter \(Q\) and then a dime \(D\) to the right of the quarter. Each coin has two sides: “heads” (denoted with the subscript \(H\))

⁴

The name “heads” probably comes from the fact that there is the picture of a famous person’s head on one side of the coin.

or “tails” (denoted with the subscript \(T\)). Each coin begins heads up. We denote this initial state \((Q_H,D_H)\text{.}\) There are two different moves:

Swap.
Swap the position of the two coins (left/right), or
Flip.
Flip one coin from heads to tails, or vice versa.

How many different states are there? List them.
How can we go from state \((Q_H,D_H)\) to state \((D_T,Q_H)\) in a sequence of moves? Is this sequence of moves unique?
Draw the graph where each vertex is labeled by a state and each move is represented by an edge.

Check.

Eight \((Q_H,D_H), (Q_H,D_T), (Q_T,D_H), \ldots,(D_T,Q_H), (D_T,Q_T)\)
Hint: It takes two moves. It is not unique because you can start with a swap and then flip, or you can start with a flip and then swap.
Hint: Each vertex should have degree three.

8. Recap.

Do you know …

What the singular of “vertices” is? Hint: we do not say “one vertice.”
What it means for two vertices in a graph to be adjacent?
What the neighbors of a vertex are?
Why are there many different graph drawings for the same graph?
How to model a story with a graph, including describing what the vertices are and what the edges represent?
How to calculate the degree of a vertex from an edge list?
How to calculate the degree of a vertex from a graph drawing?
What an isolated vertex and end vertex are?

9. Explore.

Five students applied for on-campus jobs, as listed in Table 3.1.28. Each job is willing to hire one of the students who applied. Each student can get at most one job.

Table 3.1.28. Student’s job preferences

Student	Admissions	Bookstore	Cafeteria	(tech) Desk	Events

Haloke	\(\checkmark\)	\(\checkmark\)			\(\checkmark\)

Ian	\(\checkmark\)		\(\checkmark\)		\(\checkmark\)

Jamar		\(\checkmark\)	\(\checkmark\)	\(\checkmark\)

Khanh		\(\checkmark\)		\(\checkmark\)	\(\checkmark\)

Levi			\(\checkmark\)

Could each student get a job? Explain.
Draw a graph to represent the situation. Hint: Use a vertex for each student and for each job. You might want to color the vertices that represent students in one color (say black) and the vertices that represent jobs in another color (say white). Yes, it is weird that we have objects of two types.
⁵

Officially a graph with objects of two types, as in Exercise 9, is a bipartite graph.
Highlight key edges in your graph to illustrate your answer to 9.(a).

Check.

Yes. Haloke: Admissions, Ian: Events, Jamar: Bookstore, Khanh: (tech) Desk, Levi: Cafeteria. Note that this solution is not unique. Can you find another solution?
Hint: Your graph should have five white vertices, five black vertices, and an edge for each \(\checkmark\) in Table 3.1.28.
Hint: You should highlight five edges so that each student and each job are the endpoint of exactly one highlighted edge.

Subsubsection Exercises for 3.1.C Graph Complements

10. Practice.

In a tech company, each employee typically works on several projects at a time, often with slightly different teams for each project.

Consider a graph \(C\) where the vertices are the employees and there is an edge between two vertices if the corresponding employees are on a project team together. If \(z\) is an employee working on exactly one team and that team has five other members (in addition to \(z\)), what does that tell you about the vertex \(z\text{?}\)
A manager is trying to arrange for each team to travel to that team’s main client for a day. If two project teams do not have any members in common, then they can travel on the same day. The manager draws a new graph \(D\) with the same vertices, but now there is an edge between two vertices if the corresponding employees are not on any project team together. How is the graph \(D\) related to the graph \(C\text{?}\)

11. Practice.

Consider the graphs \(G\text{,}\) \(H\text{,}\) and \(J\) drawn in Figure 3.1.31.

Draw the complement \(\overline{G}\text{.}\)
Draw the complement \(\overline{H}\text{.}\)
Draw the complement \(\overline{J}\text{.}\)

Check.

The complements are drawn in Figure 3.1.32.

12. Practice.

Draw the complement of the graph \(E\) drawn in Figure 3.1.34.

Figure 3.1.34. The graph \(E\text{.}\)
List the edges of \(E\text{.}\)
List the edges of \(\overline{E}\text{.}\)

Check.

Hint: Your complement should have six vertices and seven edges. The vertices \(s_2\) and \(s_3\) are the end vertices of the complement.
\(\{e_1,s_1\}\)\(,\{e_1,s_4\}\text{,}\) …, \(\{s_2,s_4\}\text{.}\)

13. Recap.

Do you know …

Why we might model a situation with the complement of a graph instead of the original graph?
How to find the complement of a graph?

14. Explore.

The set \(\{1,2,3\}\) has eight subsets, as defined in Definition 2.3.3. They are

\begin{equation*} \varnothing, \{1\}, \{2\}, \{3\},\{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\} \end{equation*}

Draw the graph whose vertices are these subsets where there is an edge between vertices if those subsets have at least one element in common. Which vertex is isolated?
Draw the graph whose vertices are these subsets where there is an edge between vertices if those subsets have no elements in common. Are there any isolated vertices?
How are these graphs related?

Check.

Hints: Your graph should have eight vertices and 15 edges. For example, the neighbors of \(\{1,2\}\) are \(\{1\}\text{,}\) \(\{2\} \{2,3\}\)\(,\{1,2,3\}\text{.}\) The isolated vertex is \(\varnothing\text{.}\)
Hints: Your graph should have eight vertices and 13 edges. For example, the neighbors of \(\{1,2\}\) are \(\varnothing\) and \(\{3\}\text{.}\) There is no isolated vertex.
Hint: They have opposite edges.

15. Explore.

Consider a graph \(G\) with \(n\) vertices and its complement \(\overline{G}\text{.}\) Suppose \(v\) is a vertex in \(G\text{.}\) How are \(\fn{deg}_G(v)\) and \(\fn{deg}_{\overline{G}}(v)\) related? Explain. Hint: Example 3.1.16.

Check.

Hint: For a vertex \(v\text{,}\) there are \(n-1\) other vertices each of which is a neighbor of \(v\) in \(G\) or a neighbor of \(v\) in \(\overline{G}\) (and never both). Recall that \(\fn{deg}_G(v)\) counts the number of neighbors of \(v\) in \(G\) and \(\fn{deg}_{\overline{G}}(v)\) counts the number of neighbors of \(v\) in \(\overline{G}\text{.}\)

Prev Top Next