Opening the book…
For the following exercises, identify each sequence of vertices from the figure as a walk, trail, and/or path. Select all that apply.
A → B → F → G → K → J → F → B
G → K → O → N → J → K → L
F → J → K → G → B → A
I → J → K → L → K → J → N
M → N → O → K → L → H
A → F → K → P
N → J → F → B → C → G → F → E
E → F → J → I → E
For the following exercises, identify each sequence of vertices from Figure 12.134 as a closed walk, circuit (closed trail), and/or directed cycle (closed path). Select all that apply.
A → B → F → G → K → J → F → B → A
G → K → O → N → J → K → L
F → J → N → O → K → J → I → E → F
I → J → K → G → F → E → I
M → N → O → K → J → I → M
N → J → F → B → C → G → F → J → N
A → B → G → F → E → A
E → F → G → K → J → F → B → A → E
For the following exercises, use the graphs shown. Identify the graph or graphs with the given characteristics.
The colors do not follow the definition of a graph coloring.
The graph is a two-coloring.
The graph is a three-coloring.
The graph is a four-coloring.
The graph is planar.
The graph has a chromatic number of two.
Fewer colors could be used to color the graph.
The chromatic number is more than four.
The Four-Color Theorem applies to the graph.
For the following exercises, complete the sequence of vertices from the graph to create the indicated kind of closed walk.
Closed path: a → b → □ → □ → □ → a
Closed path that visits edge ed twice: e → d → □ → □ → □ → e
Directed cycle: e → a → □ → □ → □ → e
Directed cycle: b → d → □ → □ → □ → b
Circuit that visits vertex d twice: b → c → d → □ → □ → □ → b
Circuit that visits vertex f twice: g → h → f → □ → □ → □ → g
For the following exercises, use the graphs shown.
Find the chromatic number \(n\) for graph 1 and give an \(n\)-coloring.
Find the chromatic number \(n\) for graph 2 and give an \(n\)-coloring.
Find the chromatic number \(n\) for graph 3 and give an \(n\)-coloring.
Find the chromatic number \(n\) for graph 4 and give an \(n\)-coloring.
For the following exercises, indicate the smallest and largest possible chromatic number of the graph described.
The graph has 15 vertices and contains a clique with 9 vertices.
A planar graph with 100 vertices and a clique with 3 vertices.
A planar graph with more than 2 vertices and no cliques.
A complete graph with 2,123 vertices.
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 space in the center of a five-by-five grid are shown in the first 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 the second figure is most accurately described as a closed walk, a circuit, or a directed cycle. Explain your reasoning.
An open knight’s tour on a five-by-five board is shown in the figure. Is it most accurately described as a walk, a trail, or a path?
A knight’s tour is not possible on a four-by-four board like the one shown in the figure. Find an open tour of the board in which the knight is permitted to travel through a given space more than once to achieve the goal of visiting every space. Is your tour most accurately described as a walk, trail, or path? Explain why.
The neighborhood of Pines West has three cul-de-sacs that meet at an intersection as shown in the figure. 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 walk, trail, path, closed walk, circuit, or directed cycle? Explain your reasoning.
Draw the graph for the route described in the neighborhood. Find its chromatic number. Find a map coloring that shows the chromatic number.
When radio towers are within range of each other, they must use different frequencies. In the graph, the vertices represent the towers, and the edges indicate the towers are in range of each other. Use graph colorings to determine the number of frequencies needed to avoid two towers in the same range being assigned the same frequency. Give an example of a coloring to support your conclusion.
A Sudoku puzzle consists of a nine-by-nine grid which is subdivided into nine three-by-three smaller grids. Given an incomplete grid, the goal is to complete it in such a way that each row contains the numbers 1 through 9, each column contains the numbers 1 through 9, and each three by three grid contains the numbers 1 through 9 as shown in the figure. If a graph were drawn with a vertex to represent each entry in the grid, what should the edges represent so that a nine-coloring of the graph would be a solution to the puzzle?
At a wedding reception, the bride and groom would like their family and friends to get to know each other better. They have decided that if two people know each other, they will not seat them at the same table. The following is a list of guests and who they know. Guests A, B, C, and D all know each other; guests E, F, G, and H all know each other; guests I, J, and K all know each other; guests P, Q and R all know each other, guests L, M, and O all know each other. Additionally, I knows D and I knows G, J knows M, K knows P, N knows L, and N knows O.
Draw a graph to show the relationships.
Determine the minimum number of tables needed to seat the guests so that they will sit with people they don’t know.
Give a coloring to support your conclusion.
The map of the states of Imaginaria is given. Use the figure to answer the following exercises.
Draw a graph to represent the map.
Determine the chromatic number of the graph you found.
Give a graph coloring that supports your answer in the previous question.
Color the provided map to correspond with the coloring you found in the previous question.
12.4.0: Exercises is shared under a not declared license and was authored, remixed, and/or curated by LibreTexts.
The book could not be loaded just now.