12.6.0: Exercises

Contemporary Mathematics · LibreTexts

0%

Contents

    Text

    Size
    100%
    Theme
    Typeface
    Line length
    Spacing

    From LibreTexts, under not declared, as the source states it; its equations are written in TeX, which the PDF shows typeset. This page at LibreTexts.

    Use the figure to answer the following exercises. Identify the graph(s) with the given characteristics, if any.

    Four graphs. Graph T has six vertices: a, b, c, d, e, and f. The edges connect a c, c e, e d, d a, a e, e b, b f, and f e. Graph U has eight vertices labeled a to h. The edges connect c b, b d, d h, h e, e g, g c, b a, a e, e f, f b, and g d. Graph V has four vertices, a to d. The edges connect a c, c b, b d, d a, a b, and d c. Graph W has 14 vertices labeled a to n. The edges from a lead to b, c, d, e, f, g, and h. The edges from b lead to i, j, k, l, m, and n.

    Exercise \(\PageIndex{1}\)

    Connected

    Exercise \(\PageIndex{2}\)

    All vertices of even degree

    Exercise \(\PageIndex{3}\)

    Exactly two vertices of odd degree

    Exercise \(\PageIndex{4}\)

    Has an Euler trail

    Exercise \(\PageIndex{5}\)

    Has an Euler circuit

    Exercise \(\PageIndex{6}\)

    Has neither an Euler trail nor an Euler circuit

    Exercise \(\PageIndex{7}\)

    ab is a bridge

    Exercise \(\PageIndex{8}\)

    ef is a bridge

    Exercise \(\PageIndex{9}\)

    ab is a local bridge

    Exercise \(\PageIndex{10}\)

    ef is a local bridge

    Use the figure to answer the following exercises. In each exercise, a graph and a sequence of vertices are given. Determine whether each sequence of vertices is an Euler trail, an Euler circuit, or neither for the graph. If it is neither, explain why.

    Four graphs. Graph A has two overlapping quadrilaterals, s t u v and w x y z. An edge connects w to u. Graph B has two overlapping quadrilaterals, s t z y, and r v w x. A vertex, u is at the center of r v and t z. Graph C has six vertices. The edges connect s t, t v, v w, w x, x u, w u, u s, and u t. Graph D has 10 vertices. The edges from t lead to x, r, s, u, and q. The edges from x lead to v, w, y, and z. The edges connect r s, u q, v w, and y z.
    Figure 12.176
    Exercise \(\PageIndex{11}\)

    Graph A, w → x → y → z → w → u → t → s → v → u

    Exercise \(\PageIndex{12}\)

    Graph A, u → v → s → t → u → w → z → y → x → w

    Exercise \(\PageIndex{13}\)

    Graph A, s → t → u → v → u → w → z → y → x → w

    Exercise \(\PageIndex{14}\)

    Graph A, w → x → y → z → w → v → u → t → s → v

    Exercise \(\PageIndex{15}\)

    Graph B, u → v → w → x → r → u → t → s → y → z → u

    Exercise \(\PageIndex{16}\)

    Graph B, v → w → x → r → u → z → y → s → t → u

    Exercise \(\PageIndex{17}\)

    Graph C, s → t → u → v → w → x → s

    Exercise \(\PageIndex{18}\)

    Graph C, t → u → x → w → u → s → t → v → w

    Exercise \(\PageIndex{19}\)

    Graph D, t → r → s → t → u → v → t → x → v → w → x → y → z → x

    Exercise \(\PageIndex{20}\)

    Graph D, x → v → w → x → y → z → x → t → r → s → t → u → v → t

    Use the figure to answer the following exercises. For each graph, identify a bridge if one exists. If it does not, state so. If it does, identify any components that are created when the bridge is removed.

    Four graphs. Graph A has two overlapping quadrilaterals, s t u v and w x y z. An edge connects w to u. Graph B has two overlapping quadrilaterals, s t z y, and r v w x. A vertex, u is at the center of r v and t z. Graph C has six vertices. The edges connect s t, t v, v w, w x, x u, w u, u s, and u t. Graph D has 10 vertices. The edges from t lead to x, r, s, u, and q. The edges from x lead to v, w, y, and z. The edges connect r s, u q, v w, and y z.

    Exercise \(\PageIndex{21}\)

    Graph A

    Exercise \(\PageIndex{22}\)

    Graph B

    Exercise \(\PageIndex{23}\)

    Graph C

    Exercise \(\PageIndex{24}\)

    Graph D

    Use the figuree to answer the following exercises. For each graph, identify a local bridge if one exists. If it does not, state so. If it does, find a shortest path between the vertices of the local bridge if the local bridge is removed.

    Four graphs. Graph A has two overlapping quadrilaterals, s t u v and w x y z. An edge connects w to u. Graph B has two overlapping quadrilaterals, s t z y, and r v w x. A vertex, u is at the center of r v and t z. Graph C has six vertices. The edges connect s t, t v, v w, w x, x u, w u, u s, and u t. Graph D has 10 vertices. The edges from t lead to x, r, s, u, and q. The edges from x lead to v, w, y, and z. The edges connect r s, u q, v w, and y z.

    Exercise \(\PageIndex{25}\)

    Graph A

    Exercise \(\PageIndex{26}\)

    Graph B

    Exercise \(\PageIndex{27}\)

    Graph C

    Exercise \(\PageIndex{28}\)

    Graph D

    Use the graphs to answer the following exercises. In each exercise, a graph is given. Find two Euler trails in each graph using Fleury’s algorithm.

    Three graphs. Graph Q has five vertices: c, d, e, f, and g. The edges connect c d, d e, e g, g f, f c, d f, and d g. Graph R has five vertices: h, i, j, k, and m. The edges connect h i, k, k m, m j, j h, and j k. Graph S has five vertices: n, o, p, q, and r. The edges connect n o, o q, q r, q p, r p, p o, and p n.

    Exercise \(\PageIndex{29}\)

    Graph Q

    Exercise \(\PageIndex{30}\)

    Graph R

    Exercise \(\PageIndex{31}\)

    Graph S

    Exercise \(\PageIndex{32}\)

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

    An illustration shows a 5 by 5 square chess board. The knight is at the center of the board. The knight moves in an L-shape and it is indicated by 8 arrows. It moves either two steps left or right followed by one step up or down, or two steps up or down followed by one step left or right.
    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.

    An illustration shows a 5 by 6 chessboard. Each square has a vertex. It displays several edges representing all possible knight moves. An illustration shows vertices arranged in 5 rows and 6 columns. The edges represent the knight's moves.
    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 figure is most accurately described as a trail, a circuit, an Euler trail, or an Euler circuit of the graph of all possible knight moves. Explain your reasoning.

    A graph represents a knight's moves on a 5 by 6 chessboard. The knight is at the bottom-left square. The knight moves in an L-shape. The movement of the knight inside the 5 by 6 board is mapped and connected with edges.

    Exercise \(\PageIndex{33}\)

    Determine if the open knight’s tour in the figure is most accurately described as a trail, a circuit, an Euler trail, or an Euler circuit of the graph of all possible knight moves on a five-by-five game board. Explain your reasoning.

    A graph represents a knight's moves on a 5 by 5 chessboard. The knight is at the center square of the board. The knight moves in an L-shape. The movement of the knight inside the 5 by 5 board is mapped and connected with edges.

    Exercise \(\PageIndex{34}\)

    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 trail, a circuit, an Euler trail, or an Euler circuit? Explain your reasoning.

    A map of Pines West. The map shows a start point at the center leading to three paths. Each path has six vertices. The start point is indicated by a vertex.

    Exercise \(\PageIndex{35}\)

    Recall that the bridges of Konigsberg can be represented as a multigraph as shown in the figure. We have seen that no route through Konigsberg passes over each bridge exactly once and returns to the starting point. Is there a route that passes over each bridge exactly once but does not begin and end at the same point? Explain your reasoning.

    A graph of Konigsberg Bridges has four vertices. The vertices are connected with edges forming two right cones.

    Exercise \(\PageIndex{36}\)

    The figure shows the map of the exhibits at an indoor aquarium. Use a graph in which the edges represent hallways and the vertices represent turns and intersections to explain why a visitor to the aquarium cannot start at one of the turns or intersections, passes by every exhibit exactly once, and end at one of the turns or intersections.

    A map of aquarium exhibits. The vertices are labeled A to S. The entrance is at the bottom.

    Exercise \(\PageIndex{37}\)

    The map of the states of Imaginaria is given. Use a graph to determine if it is possible to begin in one state, travel through Imaginaria crossing the border between each pair of states exactly once, and end in a different state. If it is possible, find such a route. If it is not, explain why.

    A map of Imaginaria. It has four regions: Fictionville, Illusionham, Mythbury, and Pretendstead.

    12.6.0: Exercises is shared under a not declared license and was authored, remixed, and/or curated by LibreTexts.