Skip to main content
\(\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}}\)
Mathematics LibreTexts

18.6: Graph Theory

  • Page ID
    34294
  • \( \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}}\)

    1.

    clipboard_e032b8010d0c6f99465d364eb5603f9df.png

    3.

    5.

    clipboard_ea2d27e6c4265d2350161e21174a3ad82.png

    7. The first and the third graphs are connected

    9. Bern to Frankfurt to Munchen to Berlin: 12hrs 50 min. (Though trip through Lyon, Paris and Amsterdam only adds 30 minutes)

    11. The first graph has an Euler circuit. The last two graphs each have two vertices with odd degree.

    13. One of several possible eulerizations requiring 5 duplications:

    clipboard_eaf5da7be9319b846ed672db1b9d49043.png

    17. Only the middle graph has a Hamiltonian circuit.

    19.

    1. Ft Worth, Arlington, Mesquite, Plano, Denton, Ft Worth: 183 miles
    2. Same as part a
    3. Same as part a

    21.

    1. ABDCEA
    2. ACEBDA
    3. ADBCEA

    23.

    clipboard_edbeba508cc3b2c66ec8f63a87530f2b4.png

    25.

    clipboard_e7e0355653e2ab74bdb23ef82356422b0.png


    18.6: Graph Theory is shared under a CC BY-SA 3.0 license and was authored, remixed, and/or curated by David Lippman via source content that was edited to conform to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.

    • Was this article helpful?