Skip to content

7. Graphs

  • Graphs are widely used in various fields such as electrical plants, transportation networks, communication networks, GPS tracking systems, and finding the shortest or optimal routes. They are also utilized in work assignment problems, scheduling plans and meetings, organizational structures, and many more.
  • Graph \(G\) is an ordered pair of sets \((V(G), E(G))\) where \(V(G)\) is a finite nonempty set of elements called vertices and \(E(G)\) is a set of unordered pairs of distinct elements of \(V(G)\) called edges.
  • Simple graph is a graph with no loops and no multiple edges.
  • Directed graph is a graph with directed edges.
  • Adjacent Vertices is a relation between two vertices if there is an edge between them.
  • Complete Graph is a simple graph with \(n\) vertices and exactly one edge between each pair of distinct vertices.
  • Connected Graph is a graph where there is a path between every pair of vertices, but not necessarily a direct edge between them.
  • Isomorphic Graphs if there is a one-to-one correspondence between their vertices such that two vertices are adjacent in one graph if and only if their corresponding vertices are adjacent in the other graph.
  • Subgraph is a graph \(H\) such that \(V(H) \subseteq V(G)\) and \(E(H) \subseteq E(G)\), that is a subset of the vertices and edges of \(G\) that are sufficient to satisfy the definition of a graph.
  • Induced Subgraph is a subgraph \(H\) of \(G\) such that \(E(H)\) consists of all edges of \(G\) that have both endpoints in \(V(H)\), that is, if you take a subset of the vertices from \(G\), then you must take all the edges that connect those vertices.
  • The Degree of a Vertex is the number of edges incident with it, except that a loop at a vertex contributes twice to the degree of that vertex. Each edge adds 1 to the degree of each of its endpoints, thus, each edge contributes 2 to the sum of the degrees of the vertices.
  • The sum of the degrees of the vertices is equal to \(2|E(G)|\), where \(|E(G)|\) is the number of edges in \(G\) and it is always an even number.
  • Euler Circuit is a circuit that contains every edge of a graph.
  • Euler Path is a path that contains every edge of a graph exactly once.

Walks, Paths, and Circuits

  • Walk is a finite alternating sequence of vertices and edges of the form \(v_0, e_1, v_1, e_2, v_2, ..., e_n, v_n\) where \(e_i = v_{i-1}v_i\) for \(i = 1, 2, ..., n\).
    • Open Walk is a walk that starts and ends at different vertices. It has repeated vertices and edges.
    • Closed Walk is a walk that starts and ends at the same vertex. It has repeated vertices and edges.
  • Trail: A walk with no repeated edges, but vertices can be repeated.
  • Path: A walk with no repeated vertices or edges.
  • Circuit: A closed walk with no repeated edges but can repeat vertices; must end at the same start vertex.
    • Simple Circuit: A circuit with no repeated vertices or edges except that the first and last vertices are the same.
Type Repeated Edges Repeated Vertices Start Vertex End Vertex
Walk Yes Yes Any Any
Open Walk Yes Yes Any Any
Closed Yes Yes Any Same start vertex
Trail No Yes Any Any
Path No No Any Any
Circuit No Yes Any Same start vertex
Simple Circuit No No Any Same start vertex 
flowchart TD
    A[Graph]--->B{Repeated Edges?}
    B-- Yes -->C[Walk]
    C---->D{Ends at same the start vertex?}
    D-- Yes -->E[Closed Walk]
    D-- No -->F[Open Walk]
    B-- No -->G{Repeated Vertices?}
    G-- Yes -->H{Ends at same the start vertex?}
    G-- No -->K{Ends at same the start vertex?}
    H-- Yes -->I[Circuit]
    H-- No -->J[Trail]
    K-- Yes -->L[Simple Circuit]
    K-- No -->M[Path]

Lattice Paths

  • Lattice Path: A path in the plane from \((0, 0)\) to \((n, k)\), where \(n\) and \(k\) are nonnegative integers, and each step in the path is one unit up or one unit to the right.
  • Lattice paths from start to end: The number of lattice paths from \((0, 0)\) to \((n, k)\) is \(\binom{n+k}{n}\) that is \(C(n+k, n)\) where \(C\) is the combination function.
  • Lattice paths between two points: The number of lattice paths from \((a,b)\) to \((c,d)\) is \(\binom{c-a+d-b}{c-a}\) that is \(C(c-a+d-b, c-a)\) where \(C\) is the combination function.
  • Lattice paths that does not cross a point: The number of lattice paths from \((0, 0)\) to \((n, k)\) that do not pass the point \((x,y)\):
    1. Find the number of lattice paths from \((0, 0)\) to \((x, y)\) and call it \(L00xy\).
    2. Find the number of lattice paths from \((x, y)\) to \((n, k)\) and call it \(LXyNk\).
    3. Find the total number of lattice paths from \((0, 0)\) to \((n, k)\) and call it \(total\).
    4. The number of lattice paths from \((0, 0)\) to \((n, k)\) that do not pass the point \((x,y)\) is \(total - (L00xy \times LXyNk)\).

Graph types

  • Hamiltonian Graph: A graph that contains a Hamiltonian circuit, which is a circuit that contains every vertex of the graph exactly once; except that the first and last vertices are the same.
  • Eulerian Graph: A graph that contains an Euler circuit, which is a circuit that contains every edge of the graph exactly once.
  • Tree: A connected graph with no cycles, that is acyclic.
  • Forest: A disjoint set of trees.