Skip to main content

Section Solutions for Chapter 13

Solutions to Exercise 13.1.6

13.1.6.1.a This graph has Euler tours, because it is connected and all vertices have even valency. One Euler tour is \(\displaystyle (d,f,g,j,a,d,e,i,h,b,f,c,b,i,d)\text{.}\) The following figure numbers the vertices \(\displaystyle 1,2,3,\ldots\) in the order they are visited.

Solutions to Exercise 13.2.12

13.2.12.2

  1. In the closure, we can join \(\displaystyle a\) to \(\displaystyle b\text{;}\) we can join \(\displaystyle a\) to \(\displaystyle c\text{;}\) and we can join \(\displaystyle b\) to \(\displaystyle f\text{.}\) This completes the closure, shown below. It is not easy to see from this whether or not the graph has a Hamilton cycle. In fact, it does not.

  2. The closure of this graph is \(\displaystyle K_6\text{.}\) We can easily see from this that the graph does have a Hamilton cycle. (To see that the closure is \(\displaystyle K_6\text{,}\) observe that every vertex of the graph has valency at least \(\displaystyle 2\text{.}\) Thus, the two vertices of valency \(\displaystyle 4\) can be joined to each of their non-neighbours. After doing so, every vertex has valency at least \(\displaystyle 3\text{,}\) so every vertex can be joined to every other vertex.)

13.2.12.3 Let \(\displaystyle G\) be the graph that has been shown here. Using the notation of Theorem 13.2.2, let \(\displaystyle S=\{a,f\}\text{.}\) Then \(\displaystyle |S|=2\text{,}\) but \(\displaystyle G\setminus S\) has \(\displaystyle 3\) connected components: \(\displaystyle \{b,e\}\text{,}\) \(\displaystyle \{c,h\}\text{,}\) and \(\displaystyle \{d,g\}\text{.}\) Since \(\displaystyle 3>2\text{,}\) \(\displaystyle G\) cannot have a Hamilton cycle.