Skip to main content
Mathematics LibreTexts

11: Basics of Graph Theory

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

    • 11.1: Background
      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, etc. 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.
    • 11.2: Basic Definitions, Terminology, and Notation
      Now that we have an intuitive understanding of what a graph is, it is time to make a formal definition.
    • 11.3: Deletion, Complete Graphs, and the Handshaking Lemma
      We’ll begin this section by introducing a basic operation that can change a graph (or a multigraph, with or without loops) into a smaller graph: deletion. Then, we will define a very important family of graphs, called complete graphs. Finally, we will introduce Euler's Handshaking Lemma.
    • 11.4: Graph Isomorphisms
      There is a problem with the way we have defined Kn. A graph is supposed to consist of two sets, V and E. Unless the elements of the sets are labeled, we cannot distinguish amongst them. Which of these graphs is K2 ? They can’t both be K2 since they aren’t the same graph – can they? The answer lies in the concept of isomorphisms.
    • 11.5: Summary
      This page contains the summary of the topics covered in Chapter 11.


    This page titled 11: Basics of Graph Theory is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Joy Morris.

    • Was this article helpful?