Skip to main content
Mathematics LibreTexts

6.1: Graph Theory

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

    There are several definitions that are important to understand before delving into Graph Theory. They are:

    • A graph is a picture of dots called vertices and lines called edges.
    • An edge that starts and ends at the same vertex is called a loop.
    • If there are two or more edges directly connecting the same two vertices, then these edges are called multiple edges.
    • If there is a way to get from one vertex of a graph to all the other vertices of the graph, then the graph is connected.
    • If there is even one vertex of a graph that cannot be reached from every other vertex, then the graph is disconnected.

    Example \(\PageIndex{1}\): Graph Example

    VLF0Spj5Q2aEcZXSKySpbI6h9c3V1ElNmXG7Z_itBxepjvJOa9eVW5oTKAfmsrpchUvM4uZf6kR6MXTw1npLzExu-o2jZ1e5JyO7qF-QgSnhXdpibR13V-W4T7bj_TbrUIEUX3A
    Figure \(\PageIndex{1}\): Graph 1

    In the above graph, the vertices are U, V, W, and Z and the edges are UV, VV, VW, UW, WZ1, and WZ2.

    This is a connected graph. VV is a loop. WZ1, and WZ2 are multiple edges.

    Example \(\PageIndex{2}\): Graph Example

    OJyZfdi4LNw86BgICWN_aAYnl_Fj5a63ihZzDt_2Ut_qw8V8DZVrXMB8cyx0IlIuFsM1pVTvVBUTGPaWMYGPPqi0mf3Yw_ZDkSBS0HCI2SjObbOCWmekyuFBWb_nMUqMIZ6dKGI
    Figure \(\PageIndex{2}\): Graph 2 Figure \(\PageIndex{3}\): Graph 3

    The graph in Figure \(\PageIndex{2}\) is connected while the graph in Figure \(\PageIndex{3}\) is disconnected.

    Definition: Graph Concepts and Terminology

    • Order of a Network: the number of vertices in the entire network or graph
    • Adjacent Vertices: two vertices that are connected by an edge
    • Adjacent Edges: two edges that share a common vertex
    • Degree of a Vertex: the number of edges at that vertex
    • Path: a sequence of vertices with each vertex adjacent to the next one that starts and ends at different vertices and travels over any edge only once
    • Circuit: a path that starts and ends at the same vertex
    • Bridge: an edge such that if it were removed from a connected graph, the graph would become disconnected

    Example \(\PageIndex{3}\): Graph Terminology

    _y_lsEHDvHfb6apCHznOpFm6kpviJfItZdZHIgrQCpqx5iUL-noMMqI-bMoTkI5HQHrgIg7Ph4qjWor5iCLKGWXQqCtkoRfjbxohtGrhv5no1P0xxljl9ZnBUmT_5c2cjZqBGH0
    Figure \(\PageIndex{4}\): Graph 4

    In the above graph the following is true:

    • Vertex A is adjacent to vertex B, vertex C, vertex D, and vertex E.
    • Vertex F is adjacent to vertex C, and vertex D.
    • Edge DF is adjacent to edge BD, edge AD, edge CF, and edge DE.

    The degrees of the vertices:

    A 4
    B 4
    C 4
    D 4
    E 4
    F 2

    Here are some paths in the above graph: (there are many more than listed)

    A,B,D

    A,B,C,E

    F,D,E,B,C

    Here are some circuits in the above graph: (there are many more than listed)

    B,A,D,B

    B,C,F,D,B

    F,C, E, D, F

    The above graph does not have any bridges.


    This page titled 6.1: Graph Theory is shared under a CC BY-SA 4.0 license and was authored, remixed, and/or curated by Maxie Inigo, Jennifer Jameson, Kathryn Kozak, Maya Lanzetta, & Kim Sonier via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.