Skip to main content

Exploration in Modern Mathematics

Mike Janssen

Section 5.1 Intro to Graph Theory

Motivating Questions.

In this section, we will explore the following questions.
  1. What is a graph? What are some of the basic ideas and terminology used to describe graphs?
  2. What features of the world can graphs help us study?

Subsection 5.1.1 The Bridges of Konigsberg

The study of graph theory often traces its roots to a historical problem known as the Seven Bridges of Königsberg, and its solution by the mathematician Leonhard Euler.

Investigation 5.1.1.

In the town of Königsberg in Prussia, there was a river containing two islands. The islands were connected to the banks of the river by seven bridges as seen in Figure 5.1.2. On their days off, townspeople would play a little game with themselves as they walked over the bridges: was it possible to plan a walk so that you cross each bridge once and only once?
Figure 5.1.2. The seven bridges (credit: Oscar Levin)

Subsection 5.1.2 Background and terminology

You’ve almost certainly encountered the word graph in a math class.
A relatively new (by mathematical standards) use of the word graph in mathematics involves the notion of connection. It is this notion that we will be exploring in this unit. We present a formal definition below.

Definition 5.1.4.

A graph, \(G\text{,}\) is a collection of vertices (or nodes), \(V\text{,}\) and a collection of edges, \(E\text{,}\) which are pairs of vertices. We denote the graph as \(G(V,E)\text{.}\)
This relatively simple, short definition nonetheless has deep consequences. We’ll see an example below, but note that the primary defining features of a graph \(G\) are some objects (vertices) and the connections between (some of) the objects (the edges). If a vertex \(v\) is connected to another vertex \(u\) by an edge \(vu\text{,}\) we say \(uv\) is incident to \(v\text{,}\) and we say \(u\) is adjacent to \(v\) and is in the neighborhood of \(v\text{.}\)

Example 5.1.5.

As a straightforward initial example, consider the graph \(G(V, E)\) where \(V = \{a,b,c,d\}\) and \(E = \{ab,ac,bd\}\text{.}\) This graph has four vertices, and three edges. One representation (drawing) of it is given in Figure 5.1.6.
Figure 5.1.6. One drawing of \(G\text{.}\)
As stated above, the most important feature of a graph is the connections it describes. Thus, we would say the graph in Figure 5.1.7 also represents the graph \(G\) from Figure 5.1.6.
Figure 5.1.7. Another drawing of \(G\text{.}\)

Activity 5.1.8.

In this activity, your job is to invent a graph \(G\) with the following properties. Draw it and be ready to share it. Then explain why your example meets the given criteria (e.g., for Question 4, which vertex has at least three neighbors?).
  1. Your graph should have six vertices
  2. Your graph should have ten edges
  3. There should be at least one pair of vertices between which you cannot trace a path of edges
  4. One vertex should should have at least three others in its neighborhood

Exploration 5.1.9.

We saw in the last unit that we could model changing quantities over time using discrete dynamical systems. Graphs, on the other hand, describe connections between objects. Brainstorm or research at least two or three complex, real-world situations which graphs might be helpful to model. That is, can you think of at least two or three situations in which one of the fundamental properties is connection? Briefly describe each situation in 3-4 sentences, and make clear how graphs can be used to describe these situations. If you find examples of such graphs, be ready to share.
In order to discuss the nuances of the connections modeled by a graph, we need a bit more terminology.

Definition 5.1.10.

Let \(G(V,E)\) be a graph. A vertex \(v\) in \(V\) is isolated if it has no neighbors. The number of edges incident to a vertex \(v\) is known as the degree of \(v\text{,}\) denoted \(\deg(v)\text{.}\) If between every pair of vertices in \(V\) there is a path of edges, we say \(G\) is connected. Otherwise, we say \(G\) is not connected. Each of the largest possible connected pieces of \(G\) is known as a component of \(G\text{.}\)

Exploration 5.1.11.

For this exploration, we will consider the graph \(G(V,E)\) in Figure 5.1.12.
Figure 5.1.12. A graph \(G\text{.}\)
  1. Is \(G\) connected? How many components does it have?
  2. Does \(G\) have any isolated vertices? If so, what are their degrees?
  3. What is the largest degree of a vertex in \(G\text{?}\) Which vertex/vertices have that degree?
  4. Suppose that \(G\) represents a social network; that is, the vertices represent people, and the edges represent friendship. Who are \(e\)’s friends?
  5. Still viewing \(G\) as the model of a network of friends, which pair of people do you think are more likely to become friends next: \(a\) and \(b\text{,}\) or \(c\) and \(e\text{?}\) Why?
  6. Still viewing \(G\) as the model of a network of friends, which pair of people do you think are more likely to become friends next: \(a\) and \(b\text{,}\) or \(c\) and \(h\text{?}\) Why?
In this section, we introduced the idea of a graph as essentially a network: a collection of vertices connected by edges. We thought about the types of situations that could be described with a graph, and learned some terminology that will help us ask and answer additional questions about graphs in future sections.

Exercises 5.1.3 Exercises

1.

Do some internet research about (Kevin) Bacon numbers
 1 
www.oracleofbacon.org
. What are they? How could you use a graph to model the situation described by a Bacon number? Then look up two or three people and report their Bacon numbers.

2.

Draw two different representations of the graph with vertices \(V = \set{a,b,c,d,e,f}\) and edges \(E = \set{ab,ad,df,ef,cd,be,af}\text{.}\)

3.

Do an internet search for “social graph”. What is it? How has it been used, and by whom?
PrevTopNext