Skip to main content
Engineering LibreTexts

11.3: Some Common Graphs

  • Page ID
    48368
    • Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer
    • Google and Massachusetts Institute of Technology via MIT OpenCourseWare
    \( \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}}\)

    Some graphs come up so frequently that they have names. A complete graph \(K_n\) has \(n\) vertices and an edge between every two vertices, for a total of \(n(n-1)/2\) edges. For example, \(K_5\) is shown in Figure 11.3.

    The empty graph has no edges at all. For example, the empty graph with 5 nodes is shown in Figure 11.4.

    clipboard_eeede93dc107c41629c7766b237a58eb3.png
    Figure 11.3 \(K_5\): the complete graph on 5 nodes.
    clipboard_e12790ba8574cf829db85f25d1a466406.png
    Figure 11.4 An empty graph with 5 nodes.

    An \(n\)-node graph containing \(n_1\) edges in sequence is known as a line graph \(L_n\). More formally, \(L_n\) has

    \[\nonumber V(L_n) = \{v_1, v_2, \ldots, v_n\}\]

    and

    \[\nonumber E(L_n) = \{\langle v_1 - v_2 \rangle, \langle v_2 - v_3 \rangle, \ldots, \langle v_{n-1} - v_n \rangle\}\]

    For example, \(L_5\) is pictured in Figure 11.5.

    There is also a one-way infinite line graph \(L_{\infty}\) which can be defined by letting the nonnegative integers \(\mathbb{N}\) be the vertices with edges \((k - (k + 1))\) for all \(k \in \mathbb{N}\).

    If we add the edge \(\langle v_n - v_1 \rangle\) to the line graph \(L_n\), we get a graph called a length-n cycle \(C_n\). Figure 11.6 shows a picture of length-5 cycle.

    clipboard_e9d29df8906ecc2bdddb5ff889f7801cf.png
    Figure 11.5 \(L_5\): a 5-node line graph.
    clipboard_e201db98ff49140931a039a7b197ef3b1.png
    Figure 11.6 \(C_5\): a 5-node cycle graph.

    This page titled 11.3: Some Common Graphs is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer (MIT OpenCourseWare) .

    • Was this article helpful?