Skip to main content
Mathematics LibreTexts

15.6: Exercises

  1. Last updated
  2. Save as PDF
  • Page ID
    93231

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Recognizing paths and trails.

    In each of Exercises 1–4, you are given a walk through a graph. Determine whether the walk is a path, a trail, or neither. Also determine whether the walk is open or closed.

    Example \(\PageIndex{1}\)

    \(v_1, e_1, v_2, e_2, v_3, e_3, v_4, e_{12}, v_6, e_6, v_3 \text{.}\)

    Example \(\PageIndex{2}\)

    \(v_1, e_1, v_2, e_2, v_3, e_3, v_4, e_4, v_5, e_5, v_6, e_6, v_3, e_7, v_7, e_8, v_1 \text{.}\)

    Example \(\PageIndex{3}\)

    \(v_1, e_8, v_7, e_7, v_3, e_7, v_7, e_8, v_1 \text{.}\)

    Example \(\PageIndex{4}\)

    \(v_3, e_3, v_4, e_4, v_5, e_5, v_6, e_6, v_3 \text{.}\)

    Example \(\PageIndex{5}\)

    Consider the graph in Figure \(\PageIndex{1}\).

    clipboard_e42f5b893399d9a0c6d4a641cee536f80.png
    Figure \(\PageIndex{1}\): An example graph.
    1. Determine four different paths from vertex \(1\) to vertex \(5\text{.}\)
    2. Determine four different trails from vertex \(1\) to vertex \(5\text{,}\) none of which are paths.
    3. Determine four different walks from vertex \(1\) to vertex \(5\text{,}\) none of which are trails.

    Example \(\PageIndex{6}\)

    Consider the graph in Figure \(\PageIndex{2}\).

    clipboard_e09e6de6e9d490d95416f570240040f5a.png
    Figure \(\PageIndex{2}\): An example graph.
    1. How many different trails are there from vertex \(1\) to vertex \(5\text{?}\)
    2. How many different paths are there from vertex \(1\) to vertex \(5\text{?}\) (Hint: See Proposition 15.2.1.)
    3. How many different walks are there from vertex \(1\) to vertex \(5\text{?}\)

    Recognizing bridges.

    In each of Exercises 7–10, identify each edge that is a bridge.

    Exercise \(\PageIndex{7}\)

    clipboard_e320c6e2b7dd7fbe99acad2635f7e9674.png
    Figure \(\PageIndex{3}\)

    Exercise \(\PageIndex{8}\)

    clipboard_e856886b64042326138d933fe23a3b271.png
    Figure \(\PageIndex{4}\)

    Exercise \(\PageIndex{9}\)

    clipboard_eb2ff736863453d630826d62be33e1e72.png
    Figure \(\PageIndex{5}\)

    Exercise \(\PageIndex{10}\)

    The complete graph with \(n\) vertices.

    Exercise \(\PageIndex{11}\)

    Among all possible nonconnected graphs with \(n\) vertices, let \(H\) be one with the maximum number of edges. Prove that \(H\) has exactly two connected components.

    Hint.

    Argue by contradiction.

    Exercise \(\PageIndex{12}\)

    Suppose \(G\) is a connected graph that contains a closed path that is also a trail. Prove that it is possible to remove any single edge from this path and be left with a connected subgraph of \(G\text{.}\) That is, prove that no edge in this path could be a bridge.

    Exercise \(\PageIndex{13}\)

    Prove that a graph in which every edge is a bridge cannot have a closed path that is also a trail.

    This page titled 15.6: Exercises is shared under a GNU Free Documentation License 1.3 license and was authored, remixed, and/or curated by Jeremy Sylvestre via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.