3.8.1: Exercises

Exercise \(\PageIndex{1}\)

Graph A: f → b → g → e → d → c → f

Exercise \(\PageIndex{2}\)

Graph A: g → b → f → c → d → e → g

Exercise \(\PageIndex{3}\)

Graph A: d → e → g → d → f → b → g → f → c → d

Exercise \(\PageIndex{4}\)

Graph L: h → i → k → n → j → h

Exercise \(\PageIndex{5}\)

Graph L: n → i → h → j → m → k → n

Exercise \(\PageIndex{6}\)

Graph L: j → i → n → k → i → j → k → m → j

Exercise \(\PageIndex{7}\)

Graph U: v → w → r → s → t → o → q → v

Exercise \(\PageIndex{8}\)

Graph U: w → q → r → s → t → o → v → w

Exercise \(\PageIndex{9}\)

A Hamilton cycle in Graph P that begins at vertex c.

Exercise \(\PageIndex{10}\)

An Euler circuit in Graph P that begins at vertex c.

Exercise \(\PageIndex{11}\)

A directed cycle in Graph P that is NOT a Hamilton cycle, and explain why it is not a Hamilton cycle.

Exercise \(\PageIndex{12}\)

A directed circuit in Graph P that is NOT an Euler circuit, and explain why it is not an Euler circuit.

Exercise \(\PageIndex{13}\)

A Hamilton cycle in Graph Q that begins at vertex n.

Exercise \(\PageIndex{14}\)

An Euler circuit in Graph Q that begins at vertex n.

Exercise \(\PageIndex{15}\)

A directed cycle in Graph Q that is NOT a Hamilton cycle, and explain why it is not a Hamilton cycle.

Exercise \(\PageIndex{16}\)

A directed circuit in Graph Q that is NOT an Euler circuit, and explain why it is not an Euler circuit.

Exercise \(\PageIndex{17}\)

Use the results of Exercises 9–16 to make an observation about which tends to involve a longer sequence of vertices, Hamilton cycles or Euler circuits. Explain why you think this is.

Exercise \(\PageIndex{18}\)

\(n!,\,{n} = 10\)

Exercise \(\PageIndex{19}\)

\(n!,\,{n} = 11\)

Exercise \(\PageIndex{20}\)

\(\left( {n - 1} \right)!,\,{n} = 10\)

Exercise \(\PageIndex{21}\)

\(\left( {n - 1} \right)!,\,{n} = 11\)

Exercise \(\PageIndex{22}\)

have

Exercise \(\PageIndex{23}\)

teamwork

Exercise \(\PageIndex{24}\)

anime

Exercise \(\PageIndex{25}\)

making

Exercise \(\PageIndex{26}\)

12 vertices

Exercise \(\PageIndex{27}\)

13 vertices

Exercise \(\PageIndex{28}\)

9 vertices

Exercise \(\PageIndex{29}\)

8 vertices

Exercise \(\PageIndex{30}\)

\(x\) vertices

Exercise \(\PageIndex{31}\)

\(5! = 120\) Hamilton cycles

Exercise \(\PageIndex{32}\)

\(6! = 720\) Hamilton cycles

Exercise \(\PageIndex{33}\)

\(7! = 5040\) Hamilton cycles

Exercise \(\PageIndex{34}\)

\(x!\) Hamilton cycles

Exercise \(\PageIndex{35}\)

1. b → a → c → d → b
2. b → a → d → c → b
3. b → c → a → d → b
4. b → c → d → a → b
5. b → d → a → c → b
6. b → d → c → a → b

Exercise \(\PageIndex{36}\)

1. i → f → g → h → e → i
2. i → f → g → e → h → i
3. i → f → h → g → e → i
4. i → f → h → e → g → i
5. i → f → e → g → h → i
6. i → f → e → h → g → i
7. i → g → f → h → e → i
8. i → g → f → e → h → i
9. i → g → h → f → e → i
10. i → g → h → e → f → i
11. i → g → e → f → h → i
12. i → g → e → h → f → i
13. i → h → g → f → e → i
14. i → h → g → e → f → i
15. i → h → f → g → e → i
16. i → h → f → e → g → i
17. i → h → e → g → f → i
18. i → h → e → f → g → i
19. i → e → g → h → f → i
20. i → e → g → f → h → i
21. i → e → h → g → f → i
22. i → e → h → f → g → i
23. i → e → f → g → h → i
24. i → e → f → h → g → i

Exercise \(\PageIndex{37}\)

q → r → s → v → y → x → w → t → u → q

Exercise \(\PageIndex{38}\)

u → y → x → w → t → q → r → s → v → u

Exercise \(\PageIndex{39}\)

y → v → s → r → u → q → t → w → x → y

Exercise \(\PageIndex{40}\)

u → v → s → r → q → t → w → x → y → u

Exercise \(\PageIndex{41}\)

The neighborhood of Pines West has three cul-de-sacs that meet at an intersection as shown. A postal delivery person starts at the intersection and visits each house in a cul-de-sac once, returns to the intersection, visits each house in the next cul-de-sac, and so on, returning to the intersection when finished. Describe how the route can be represented as a graph. If there is no backtracking, in other words, the person never reverses direction, is the route followed by the postal delivery person best described as a trail, an Euler circuit, a Hamilton cycle, or neither? Explain your reasoning.

Exercise \(\PageIndex{42}\)

In chess, a knight can move in any direction, but it must move two spaces then turn and move one more space. The 8 possible moves a knight can make from a given space are shown in the figure.

A graph in which each vertex represents a space on a five-by-six game board and each edge represents a move a knight could make is shown in the figure.

A knight’s tour is a sequence of moves by a knight on a chessboard (of any size) such that the knight visits every square exactly once. If the knight’s tour brings the knight back to its starting position on the board, it is called a closed knight’s tour. Otherwise, it is called an open knight’s tour.

Determine if the closed knight’s tour in Figure 12.239 is most accurately described as an Euler circuit or a Hamilton cycle, or both, of the graph of all possible knight moves. Explain your reasoning.