1.
-
What is the degree of vertex \(8\text{?}\)
-
What is the degree of vertex \(10\text{?}\)
Exercises 5.9 Exercises
2.
Draw a graph with \(8\) vertices, all of odd degree, that does not contain a path of length \(3\) or explain why such a graph does not exist.
3.
Draw a graph with \(6\) vertices having degrees \(5\text{,}\) \(4\text{,}\) \(4\text{,}\) \(2\text{,}\) \(1\text{,}\) and \(1\) or explain why such a graph does not exist.
4.
For the next Olympic Winter Games, the organizers wish to expand the number of teams competing in curling. They wish to have \(14\) teams enter, divided into two pools of seven teams each. Right now, they’re thinking of requiring that in preliminary play each team will play seven games against distinct opponents. Five of the opponents will come from their own pool and two of the opponents will come from the other pool. They’re having trouble setting up such a schedule, so they’ve come to you. By using an appropriate graph-theoretic model, either argue that they cannot use their current plan or devise a way for them to do so.
5.
For this exercise, consider the graph \(\bfG\) in Figure 5.47.
-
Let \(V_1=\{g,j,c,h,e,f\}\) and \(E_1=\{ge,jg,ch,ef\}\text{.}\) Is \((V_1,E_1)\) a subgraph of \(\bfG\text{?}\)
-
Let \(V_2=\{g,j,c,h,e,f\}\) and \(E_2=\{ge,jg,ch,ef,cj\}\text{.}\) Is \((V_2,E_2)\) a subgraph of \(\bfG\text{?}\)
-
Let \(V_3=\{a,d,c,h,b\}\) and \(E_3=\{ch,ac,ad,bc\}\text{.}\) Is \((V_3,E_3)\) an induced subgraph of \(\bfG\text{?}\)
6.
7.
Figure 5.48 contains four graphs on six vertices. Determine which (if any) pairs of graphs are isomorphic. For pairs that are isomorphic, give an isomorphism between the two graphs. For pairs that are not isomorphic, explain why.
8.
9.
Consider the graph \(\bfG\) in Figure 5.50. Determine if the graph is eulerian. If it is, find an eulerian circuit. If it is not, explain why it is not. Determine if the graph is hamiltonian. If it is, find a hamiltonian cycle. If it is not, explain why it is not.
10.
Explain why the graph \(\bfG\) in Figure 5.51 does not have an eulerian circuit, but show that by adding a single edge, you can make it eulerian.
11.
An eulerian trail is defined in the same manner as an eulerian circuit (see Section 5.3) except that we drop the condition that \(x_0=x_t\text{.}\) Prove that a graph has an eulerian trail if and only if it is connected and has at most two vertices of odd degree.
12.
Alice and Bob are discussing a graph that has \(17\) vertices and \(129\) edges. Bob argues that the graph is hamiltonian, while Alice says that he’s wrong. Without knowing anything more about the graph, must one of them be right? If so, who and why, and if not, why not?
13.
Find the chromatic number of the graph \(\bfG\) in Figure 5.52 and a coloring using \(\chi(\bfG)\) colors.
14.
Find the chromatic number of the graph \(\bfG\) in Figure 5.53 and a coloring using \(\chi(\bfG)\) colors.
15.
A pharmaceutical manufacturer is building a new warehouse to store its supply of \(10\) chemicals it uses in production. However, some of the chemicals cannot be stored in the same room due to undesirable reactions that will occur. The matrix below has a \(1\) in position \((i,j)\) if and only if chemical \(i\) and chemical \(j\) cannot be stored in the same room. Develop an appropriate graph theoretic model and determine the smallest number of rooms into which they can divide their warehouse so that they can safely store all \(10\) chemicals in the warehouse.
\begin{equation*}
\begin{bmatrix}0 \amp 1 \amp 0 \amp 1 \amp 1 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0\\
1 \amp 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1\\
0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 1 \amp 1 \amp 0\\
1 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0\\
1 \amp 1 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0\\
0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 1\\
1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 1 \amp 0 \amp 0\\
0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0\\
0 \amp 0 \amp 1 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0\\
0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0
\end{bmatrix}
\end{equation*}
16.
A school is preparing the schedule of classes for the next academic year. They are concerned about scheduling calculus, physics, English, statistics, economics, chemistry, and German classes, planning to offer a single section of each one. Below are the lists of courses that each of six students must take in order to successfully graduate. Determine the smallest number of class periods that can be used to schedule these courses if each student can take at most one course per class period. Explain why fewer class periods cannot be used.
| Student | Courses |
| 1 | Chemistry, Physics, Economics |
| 2 | English, German, Statistics |
| 3 | Statistics, Calculus, German |
| 4 | Chemistry, Physics |
| 5 | English, Chemistry |
| 6 | Chemistry, Economics |
17.
All trees with more than one vertex have the same chromatic number. What is it, and why?
18.
Find a proper \((t+1)\)-coloring of the graph \(\bfG_{t+1}\) in Mycielski’s proof of Proposition 5.25. This establishes that \(\chi(\bfG_{t+1})\leq t+1\text{.}\)
19.
How many vertices does the graph \(\bfG_4\) from the Kelly and Kelly proof of Proposition 5.25 have?
20.
21.
Find a recursive formula for the number of vertices \(n_t\) in the graph \(\bfG_t\) from the Kelly and Kelly proof of Proposition 5.25.
22.
Let \(b_t\) be the number of vertices in the graph \(\bfG_t\) from the Mycielski’s proof of Proposition 5.25. Find a recursive formula for \(b_t\text{.}\)
23.
The girth of a graph \(\bfG\) is the number of vertices in a shortest cycle of \(\bfG\text{.}\) Find the girth of the graph \(\bfG_t\) in the Kelly and Kelly proof of Proposition 5.25 and prove that your answer is correct. As a challenge, see if you can modify the construction of \(\bfG_t\) to increase the girth. If so, how far are you able to increase it?
24.
Use the First Fit algorithm to color the graph in Figure 5.26 using the two different orderings of the vertex set shown there.
25.
Draw the interval graph corresponding to the intervals in Figure 5.54.
26.
Use the First Fit coloring algorithm to find the chromatic number of the interval graph whose interval representation is shown in Figure 5.54 as well as a proper coloring using as few colors as possible.
27.
-
From Exercise 5.9.24 you know that choosing a bad ordering of the vertices of a graph can lead to the First Fit coloring algorithm producing a coloring that is far from optimal. However, you can use this algorithm to prove a bound on the chromatic number. Show that if every vertex of \(\bfG\) has degree at most \(D\text{,}\) then \(\chi(\bfG)\leq D+1\text{.}\)
-
Give an example of a bipartite graph with \(D=1000\) to show that this bound need not be tight.
28.
Is the graph in Figure 5.53 planar? If it is, find a drawing without edges crossings. If it is not give a reason why it is not.
29.
Is the graph in Figure 5.55 planar? If it is, find a drawing without edge crossings. If it is not give a reason why it is not.
30.
Find a planar drawing of the graph \(\bfK_5-e\text{,}\) by which we mean the graph formed from the complete graph on \(5\) vertices by deleting any edge.
31.
32.
Show that every planar graph has a vertex that is incident to at most five edges.
33.
Let \(\GVE\) be a graph with \(V=\{v_1,v_2,\dots,v_n\}\text{.}\) Its degree sequence is the list of the degrees of its vertices, arranged in nonincreasing order. That is, the degree sequence of \(\mathbf{G}\) is \((\deg_\mathbf{G}(v_1),\deg_\mathbf{G}(v_2),\dots,\deg_\mathbf{G}(v_n))\) with the vertices arranged such that \(\deg_\mathbf{G}(v_1) \geq \deg_\mathbf{G}(v_2)\geq \cdots\geq \deg_\mathbf{G}(v_n)\text{.}\) Below are five sequences of integers (along with \(n\text{,}\) the number of integers in the sequence). Identify
-
the one sequence that cannot be the degree sequence of any graph;
-
the two sequences that could be the degree sequence of a planar graph;
-
the one sequence that could be the degree sequence of a tree;
-
the one sequence that is the degree sequence of an eulerian graph; and
-
the one sequence that is the degree sequence of a graph that must be hamiltonian.
Explain your answers. (Note that one sequence will get two labels from above.)
34.
Below are three sequences of length \(10\text{.}\) One of the sequences cannot be the degree sequence (see Exercise 5.9.33) of any graph. Identify it and say why. For each of the other two, say why (if you have enough information) a connected graph with that degree sequence
-
is definitely hamiltonian/cannot be hamiltonian;
-
is definitely eulerian/cannot be eulerian;
-
is definitely a tree/cannot be a tree; and
-
is definitely planar/cannot be planar.
(If you do not have enough information to make a determination for a sequence without having specific graph(s) with that degree sequence, write “not enough information” for that property.)
-
\(\displaystyle (6,6,4,4,4,4,2,2,2,2)\)
-
\(\displaystyle (7,7,7,7,6,6,6,2,1,1)\)
-
\(\displaystyle (8,6,4,4,4,3,2,2,1,1)\)
35.
For the two degree sequences in Exercise 5.9.34 that correspond to graphs, there were some properties for which the degree sequence was not sufficient information to determine if the graph had that property. For each of those situations, see if you can draw both a graph that has the property and a graph that does not have the property.
36.
37.
38.
39.
40.
41.
42.
Construct the labeled tree \(\bfT\) with Prüfer code (using commas to separate symbols in the string, since we have labels greater than \(9\)) \(10,1,7,4,3,4,10,2,2,8\text{.}\)
43.
(Challenge problem) When \(\GVE\) is a graph, let \(\Delta(\bfG)\) denote the maximum degree in \(\bfG\text{.}\) Prove Brooks’ Theorem: If \(\bfG\) is connected and \(\Delta(\bfG)=k\text{,}\) then \(\chi(\bfG)\le k+1\text{.}\) Furthermore, equality holds if and only if (a) \(k=2\) and \(\bfG\) is an odd cycle, or (b) \(k\neq2\) and \(\bfG=\bfK_{k+1}\text{.}\)
Hint.
Hint: It’s clear that \(\chi(\bfG)\le k+1\) (in fact, this was already assigned as an exercise). Assume that \(\chi(\bfG)=k+1\) but that neither conclusion (a) or (b) holds. Take a spanning tree of \(\bfG\) and an appropriate ordering of the vertices, with two leaves of the tree coming first. Then show that a First Fit coloring of the graph will only use \(k\) colors.
