5.9: Exercises

1. The questions in this exercise pertain to the graph G shown in Figure 5.46.

Figure 5.46. A graph

a. What is the degree of vertex 8?

b. What is the degree of vertex 10?

c. How many vertices of degree 2 are there in \(G\)? List them.

d. Find a cycle of length 8 in \(G\).

e. What is the length of a shortest path from 3 to 4?

f. What is the length of a shortest path from 8 to 7?

g. Find a path of length 5 from vertex 4 to vertex 6.

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, 4, 4, 2, 1, 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 \(G\) in Figure 5.47.

a. Let \(V_1 = \{g,j,c,h,e,f\}\) and \(E_1 = \{ge,jg,ch,ef\}\). Is \((V_1, E_1)\) a subgraph of \(G\)?

b. Let \(V_2 = \{g,j,c,h,e,f\}\) and \(E_2 = \{ge,jg,ch,ef,cj\}\). Is \((V_2,E_2)\) a subgraph of \(G\)?

c. Let \(V_3 = \{a,d,c,h,b\}\) and \(E_3 = \{ch,ac,ad,bc\}\). Is \((V_3,E_3)\) an induced subgraph of \(G\)?

d. Draw the subgraph of \(G\) induced by \(\{g,j,d,a,c,i\}\).

e. Draw the subgraph of \(G\) induced by \(\{c,h,f,i,j\}\).

f. Draw a subgraph of \(G\) having vertex set \(\{e,f,b,c,h,j\}\) that is not an induced subgraph.

g. Draw a spanning subgraph of \(G\) with exactly 10 edges.

Figure 5.47. A graph \(G\)

6. Prove that every tree on \(n\) vertices has exactly \(n−1\) edges.

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.

Figure 5.48. Are these graphs isomorphic?

8. Find an eulerian circuit in the graph \(G\) in Figure 5.49 or explain why one does not exist.

Figure 5.49. A graph \(G\)

9. Consider the graph \(G\) 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.

Figure 5.50. A graph \(G\)

10. Explain why the graph \(G\) in Figure 5.51 does not have an eulerian circuit, but show that by adding a single edge, you can make it eulerian.

Figure 5.51. A graph \(G\)

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\). 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 \(G\) in Figure 5.52 and a coloring using \(\chi(G)\) colors.

Figure 5.52. A graph \(G\) to color

14. Find the chromatic number of the graph \(G\) in Figure 5.53 and a coloring using \(\chi(G)\) colors.

Figure 5.53. A graph \(G\) to color

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.

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 \(G_{t+1}\) in Mycielski's proof of Proposition 5.25. This establishes that \(\chi(G_{t+1}) < t+1\).

19. How many vertices does the graph \(G_4\) from the Kelly and Kelly proof of Proposition 5.25 have?

20. Construct and draw the graph \(G_5\) from Mycielski's proof of Proposition 5.25.

21. Find a recursive formula for the number of vertices nt in the graph \(G_t\) from the Kelly and Kelly proof of Proposition 5.25.

22. Let \(b_t\) be the number of vertices in the graph \(G_t\) from the Mycielski's proof of Proposition 5.25. Find a recursive formula for \(b_t\).

23. The girth of a graph \(G\) is the number of vertices in a shortest cycle of \(G\). Find the girth of the graph \(G_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 \(G_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.

Figure 5.54. A collection of intervals

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.

a. 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 \(G\) has degree at most \(D\), then \(\chi(G) \leq D + 1\).

b. 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.

Figure 5.55. Is this graph planar?

30. Find a planar drawing of the graph \(K_{5−e}\), by which we mean the graph formed from the complete graph on 5 vertices by deleting any edge.

31. Exhibit a planar drawing of an eulerian planar graph with 10 vertices and 21 edges.

32. Show that every planar graph has a vertex that is incident to at most five edges.

33. Let \(G=(V,E)\) be a graph with \(V=\{v_1,v_2,…,v_n\}\). Its degree sequence is the list of the degrees of its vertices, arranged in nonincreasing order. That is, the degree sequence of \(G\) is \((deg_G⁡(v_1),deg_G⁡(v_2),…,deg_G⁡(v_n))\) with the vertices arranged such that \(deg_G⁡(v_1) \geq deg_G⁡(v_2) \geq \cdot \cdot \cdot \geq deg_G⁡(v_n). Below are five sequences of integers (along with \(n\), 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
• 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.)

a. \(n=10: (4,4,2,2,1,1,1,1,1,1)\)

b. \(n=9: (8,8,8,6,4,4,4,4,4)\)

c. \(n=7: (5,4,4,3,2,1,0)\)

d. \(n=10: (7,7,6,6,6,6,5,5,5,5)\)

e. \(n=6: (5,4,3,2,2,2)\)

34. Below are three sequences of length .10. 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
• 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.)

a. \((6,6,4,4,4,4,2,2,2,2)\)

b. \((7,7,7,7,6,6,6,2,1,1)\)

c. \((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. Draw the 16 labeled trees on 4 vertices.

37. Determine prüfer(T) for the tree \(T\) in Figure 5.56.

Figure 5.56. A 10-vertex tree

38. Determine prüfer(T) for the tree \(T\) in Figure 5.57.

Figure 5.57. A 10-vertex tree

39. Determine prüfer(T) for the tree \(T\) Figure 5.58.

Figure 5.58. A 14-vertex tree

40. Construct the labeled tree \(T\) with Prüfer code 96113473.

41. Construct the labeled tree \(T\) with Prüfer code 23134.

42. Construct the labeled tree \(T\) 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\)

43. (Challenge Problem)

When \(G=(V,E)\) is a graph, let \(Δ(G)\) denote the maximum degree in \(G\). Prove Brooks' Theorem: If \(G\) is connected and \(Δ(G)=k\), then \(\chi(G) \leq k+1\). Furthermore, equality holds if and only if (a) \(k=2\) and \(G\) is an odd cycle, or (b) \(k \neq 2\) and \(G = K_{k+1}\).

Hint

It's clear that \(\chi(G) \leq k+1\) (in fact, this was already assigned as an exercise). Assume that \(\chi(G)=k+1\) but that neither conclusion (a) or (b) holds. Take a spanning tree of \(G\) 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.