Skip to main content
Mathematics LibreTexts

11.1: Background

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

    In combinatorics, what we call a graph has nothing to do with the \(x\) and \(y\) axes, and plotting. Here, a graph is the most straightforward way you could think of to model a network. A network could be a computer network, a road network, a telephone network; it doesn’t matter what kind of network it is. Conceptually, any network consists of a bunch of things (let’s call them nodes) that are being connected in some fashion. To model this, we draw some points for the nodes, and we draw edges between nodes that have a direct connection.

    Leonhard Euler laid the foundations of graph theory in \(1735\), with his solution to the Königsberg bridge problem. Königsberg, Prussia (now Kaliningrad, Russia) was a city on the river Pregel. The city included two islands in the river, as well as land on both sides of the river, and there were seven bridges connecting the various parts of the city. The lay-out of the city and its bridges looked something like this:

    clipboard_e7b7b5720e4c11a43a2bd473d8413765e.png

    The question had been posed: is it possible for residents of Königsberg, out for Sunday strolls, to cross each of the seven bridges exactly once? Better yet, can they do this and end up in the same part of the city where they started?

    Euler modeled the problem using a graph, with a vertex for each part of the city (one for each bank, and one for each island), and edges representing the bridges. His model looked like this:

    clipboard_e5b6f7771da61fab387f50f98769b3e95.png

    The nodes \(A\) and \(C\) represent the two banks of the river, while \(B\) and \(D\) represent the islands. In the model, the question becomes can we trace all of the edges of this graph, without lifting our pen from the paper or going over an edge more than once?

    Euler was actually able to find an easy method you can use on any graph, to quickly work out whether or not this can be done for that graph. Also, unlike what we saw in the Pigeonhole Principle, his method is constructive: if it can be done, his method shows you how to do it. We’ll go over this method later, in Chapter 13.


    This page titled 11.1: Background is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Joy Morris.

    • Was this article helpful?