Skip to main content
Logo image

Discrete Mathematics: An Open Introduction, 4th edition

Oscar Levin

Worksheet Preview Activity
A4US

To get a feel for graphs and the types of questions we want to ask about them, let’s explore four examples of graphs.
\(G_1\text{:}\)
\(G_2\text{:}\)
Petersen graph: ten vertices each with three edges. Five of the vertices form a 5-pointed star, the other five a pentagon, edges connecting the vertices of the star and the pentagon.
A graph with six vertices arranged in two rows of three. The top vertices are labeled v1, v2, v3 from left to right. The bottom vertices are labeled v6, v5, v4 from left to right. Three edges connect each vertex in the top row to the vertex below it. Four more edges connect vertices on the top row and along the bottom row in two X configurations.
\(G_3\text{:}\)
\(G_4\text{:}\)
vertex adjacent to
\(a\) \(b, c\)
\(b\) \(a,f\)
\(c\) \(a, d, e\)
\(d\) \(c,e,f\)
\(e\) \(c,d\)
\(f\) \(b,d\)
\begin{equation*} \begin{pmatrix} 0 \amp 0 \amp 1 \amp 0 \amp 1 \amp 0 \\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \\ 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \\ 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 1 \\ 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \\ 0 \amp 1 \amp 0 \amp 1 \amp 0 \amp 0 \end{pmatrix} \end{equation*}
The graph \(G_3\) is presented as an adjacency list where each vertex gets a list of which other vertices it is adjacent to. The graph \(G_4\) is presented as an adjacency matrix where the rows and columns correspond to the vertices and the entries are 1 if the vertices are adjacent and 0 otherwise. Before answering the questions below, it might be helpful to draw a more traditional representation of these graphs.
1.
First, let’s count the number of vertices and edges in each graph.
Number of vertices: \(G_1\text{:}\) ; \(G_2\text{:}\) ; \(G_3\text{:}\) ; \(G_4\text{:}\) .
Number of edges: \(G_1\text{:}\) ; \(G_2\text{:}\) ; \(G_3\text{:}\) ; \(G_4\text{:}\) .
2.
We call that the number of edges incident to a particular vertex (i.e., the number of edges “coming out of” the vertex) the degree of the vertex. A list the degrees of all the vertices in non-increasing order is called a degree sequence for the graph. Find the degree sequence for each graph.
\(G_1\) has degree sequence: .
\(G_2\) has degree sequence: .
\(G_3\) has degree sequence: .
\(G_4\) has degree sequence: .
3.
We often care about paths between vertices in a graph. A graph is connected if there is a path between every pair of vertices. Sometimes there is a path that starts at a vertex and eventually comes back to itself, which is called a cycle.
(a)
Which of the graphs are connected?
  • \(\displaystyle G_1\)
  • \(\displaystyle G_2\)
  • \(\displaystyle G_3\)
  • \(\displaystyle G_4\)
  • None of the above
(b)
Which of the graphs contain cycles?
  • \(\displaystyle G_1\)
  • \(\displaystyle G_2\)
  • \(\displaystyle G_3\)
  • \(\displaystyle G_4\)
  • None of the above
(c)
Graphs that are connected and contain no cycles are called trees. For each graph, how many edges must you remove to turn it into a tree? (If it is already a tree, the answer would be 0.)
\(G_1\text{:}\) ; \(G_2\text{:}\) ; \(G_3\text{:}\) ; \(G_4\text{:}\) .
4.
For which of the graphs is it possible to draw the graph in such a way that no edges cross?
  • \(\displaystyle G_4\)
  • \(\displaystyle G_1\)
  • \(\displaystyle G_3\)
  • \(\displaystyle G_2\)
  • None of the above
5.
Suppose we color each vertex of a graph so that adjacent vertices always have different colors. The smallest number of colors needed to do this is called the chromatic number of the graph. Find the chromatic number for each graph.
\(G_1\text{:}\) ; \(G_2\text{:}\) ; \(G_3\text{:}\) ; \(G_4\text{:}\) .
Note: If the graphs represented friendships between people, then the chromatic number would tell us the minimum number of groups we would need if we wanted to divide up everyone into groups of people who were not yet friends.
PrevTopNext