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

    For the following exercises, use the figure showing Diagrams A, B, C, and D.

    Four diagrams are labeled Diagram A, Diagram B, Diagram C, and Diagram D. Diagram A has two vertices. The vertices are connected by an edge. One of the vertices has a loop. Diagram B has four vertices. Two vertices are connected by an edge. The remaining two vertices are connected by an edge to form an X. Diagram C has two vertices. The vertices have a double edge. Diagram D has four vertices. The vertices are connected in a cyclic form.

    Exercise \(\PageIndex{1}\)

    Identify any multigraphs.

    Exercise \(\PageIndex{2}\)

    Identify any graphs.

    Exercise \(\PageIndex{3}\)

    Identify any multigraph that has a loop.

    Exercise \(\PageIndex{4}\)

    Identify any multigraph that has a double edge.

    For the following exercises, use the figure showing Graphs S, T, U, V, and W.

    Five graphs are labeled graph S, graph T, graph U, graph V, and graph W. Graph S has five vertices: a, b, c, d, and e. The edges connect a b, a c, b c, c d, c e, and d e. Graph T has four vertices: a, b, d, and e. The edges connect a b, a e, b d, and d e. Graph U has 6 vertices: a, b, f, c, d, and e. The vertices connect a b, a f, f d, b c, c d, d e, c e, and a c. Graph V has four vertices: a, b, d, and e. The edges connect a b, a d, a e, b d, and d e. Graph W has four vertices: a, b, d, and e. The edges connect a b, a d, and d e.

    Exercise \(\PageIndex{5}\)

    Determine the number of vertices in Graph T.

    Exercise \(\PageIndex{6}\)

    Determine the number of vertices in Graph U.

    Exercise \(\PageIndex{7}\)

    Identify the graph with the most vertices.

    Exercise \(\PageIndex{8}\)

    Identify the graphs with four vertices.

    Exercise \(\PageIndex{9}\)

    Identify the graph with the most edges.

    Exercise \(\PageIndex{10}\)

    Identify the graph with the fewest edges.

    Exercise \(\PageIndex{11}\)

    Name the vertices in Graph S.

    Exercise \(\PageIndex{12}\)

    Name the vertices in Graph V.

    Exercise \(\PageIndex{13}\)

    Determine the number of edges in Graph U.

    Exercise \(\PageIndex{14}\)

    Determine the number of edges in Graph T.

    Exercise \(\PageIndex{15}\)

    Name the edges in Graph V.

    Exercise \(\PageIndex{16}\)

    Name the edges in Graph W.

    Exercise \(\PageIndex{17}\)

    Identify any pairs of vertices in Graph T that are not adjacent.

    Exercise \(\PageIndex{18}\)

    Identify any vertices in Graph V that are not adjacent.

    Exercise \(\PageIndex{19}\)

    Find the degree of vertex a in graph U.

    Exercise \(\PageIndex{20}\)

    Find the degree of vertex a in graph S.

    Exercise \(\PageIndex{21}\)

    Which two graphs have a vertex of degree 4?

    For the following exercises, use the figure showing Graphs A, B, C, and D.

    Four graphs are labeled graph A, graph B, graph C, and graph D. Graph A shows edges connecting the vertices: v q, v p, v u, v t, v s and v r. Graph B shows edges connecting the vertices: p q, q s, s t, t p, v u, and v r. Graph C shows edges connecting the vertices: p q, p u, u t, u v, t s, q s, and p t. Graph D shows edges connecting the vertices: v p, v q, v u, v t, v r, v s, p q, u t, and r s.

    Exercise \(\PageIndex{22}\)

    Identify the graph with 1 vertex of degree 6 and 6 vertices of degree 1.

    Exercise \(\PageIndex{23}\)

    Identify the graph with 1 vertex of degree 6 and 6 vertices of degree 2.

    Exercise \(\PageIndex{24}\)

    Identify the graph with exactly 1 vertex of degree 0.

    Exercise \(\PageIndex{25}\)

    Identify the graph with exactly 2 vertices of degree 1.

    Exercise \(\PageIndex{26}\)

    Name all the pairs of adjacent vertices in Graph B.

    Exercise \(\PageIndex{27}\)

    Name all the pairs of adjacent vertices in Graph A.

    Exercise \(\PageIndex{28}\)

    Identify the graph in which the sum of the degrees of the vertices is 14.

    For each of the following exercises, a scenario is given. Explain how a graph or multigraph might be drawn to model the scenario by identifying the objects that could be represented by vertices and the connections that could be represented by edges. Indicate whether a graph or a multigraph would be a better model.

    Exercise \(\PageIndex{29}\)

    The Centers for Disease Control and Prevention (CDC) is tracking the spread of a virus. The CDC is attempting to determine where the virus began by identifying where each known carrier contracted the virus.

    Exercise \(\PageIndex{30}\)

    The faculty members in a college mathematics department have a “telephone tree” that assigns each faculty member two other faculty members to call with information in the event of an emergency. The chairperson of the department contacts two faculty members. Each of these faculty members contacts two faculty members, and so on, until all faculty members have been notified.

    Exercise \(\PageIndex{31}\)

    There is a theory that any two people on earth are no more than six social connections apart, which is known as “six degrees of separation” or the “six handshake rule.” It means that there is a chain of a “friend of a friend” that connects any two people through at most six steps.

    Exercise \(\PageIndex{32}\)

    The U.S. Postal Service has a network of post offices that move mail around the United States. Mail trucks from one post office follow routes deliver mail to other locations. These mail trucks also pick up mail to bring back to their home post office.

    In the following exercises , draw a graph to represent the given scenario.

    Exercise \(\PageIndex{33}\)

    Draw a graph to model the scenario described in Your Turn 12.5.

    Exercise \(\PageIndex{34}\)

    In the game of chess, a king can move one space in any direction, vertically, horizontally, or diagonally, as indicated in the figure. Draw a graph to represent the possible movements of a king on a three-by-three section of a chess board such that each edge represents one move, and each vertex represents a position where the king might be at the beginning or end of a turn. Assume that the king can have unlimited turns.

    A 3 by 3 square chess board. The king is in the center square. Arrows from the king point to all the adjacent squares.

    Exercise \(\PageIndex{35}\)

    Chloe is interested to know how many in her network of Roblox friends are also friends with each other, so she polls them. The following is a list of each of Chloe’s friends and their common friends. Create a graph of the Roblox friends in Chloe’s network, including Chloe.

    • Aria is friends with no one else in Chloe’s network.
    • Benicio is friends with Dakshayani, Eun-ah, and Fukashi.
    • Dakshayani is friends with Benicio.
    • Eun-ah is friends with Benicio and Fukashi.
    • Fukashi is friends with Benicio and Eun-ah.

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