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