Graph Types & Master Taxonomy

Graphs model arbitrary non-linear relational topology without the hierarchical constraints of trees, capturing asymmetric dependencies, cyclic flows, and multidimensional networks. Master the mathematical invariants—from Euler's Handshaking Lemma and directed degree balances to the Odd Cycle Bipartiteness Theorem—that dictate every downstream graph algorithm.

Originating with Leonhard Euler's 1736 resolution of the Seven Bridges of Königsberg problem, Graph Theory formalizes pairwise relations between objects. A graph $G=(V,E)$ consists of a set of vertices $V$ connected by edges $E$. Unlike trees, graphs permit arbitrary cycles, multiple disjoint components, and asymmetric traversals.

By the end of this chapter, you will be able to:

1. Apply Euler's Handshaking Lemma to prove vertex degree parity invariants in undirected and directed networks.
2. Differentiate directed, undirected, weighted, and unweighted graphs across mathematical formalisms and algorithmic constraints.
3. Formulate the structural conditions of Directed Acyclic Graphs (DAGs) and their role as topological dependency engines.
4. Prove Kőnig's Odd Cycle Theorem and verify graph bipartiteness via 2-color BFS/DFS in $O(V+E)$ time.
5. Classify special topological families—including Complete ($K_n$), Planar ($V-E+F=2$), Eulerian ($O(V+E)$), and Hamiltonian (NP-Complete) graphs.

A graph $G=(V,E)$ is defined by:

• A finite vertex set $V=\{v_1,v_2,\dots ,v_n\}$.
• An edge set $E\subseteq V\times V$, where each edge connects a pair of vertices $(u,v)$.

In any undirected graph $G=(V,E)$, the sum of the degrees of all vertices equals exactly twice the number of edges:

Formal Proof

1. Each individual edge $e=(u,v)$ has exactly two endpoints ($u$ and $v$).
2. When summing vertex degrees ${\sum }_{v\in V}\mathrm{deg}(v)$, every incident edge contributes $+1$ to $\mathrm{deg}(u)$ and $+1$ to $\mathrm{deg}(v)$.
3. Because every edge is counted exactly twice, the sum equals $2|E|$. $■$

Corollary: The Odd Degree Parity Invariant

In any undirected graph, the count of vertices having an odd degree must be even.

Proof: Partition $V$ into vertices with even degrees ($V_{\text{even}}$) and odd degrees ($V_{\text{odd}}$):

The total $2|E|$ is even, and ${\sum }_{v\in V_{\text{even}}}\mathrm{deg}(v)$ is even. Thus, ${\sum }_{u\in V_{\text{odd}}}\mathrm{deg}(u)$ must be an even number. The sum of odd integers is even if and only if the number of terms is even. Hence, $|V_{\text{odd}}|$ is even. $■$

In a weighted graph, every edge $e=(u,v)$ carries an assigned numerical weight $w(e)\in \mathbb{R}$:

A Directed Acyclic Graph (DAG) is a directed graph containing no directed cycles: following directed edges from any vertex $v$ never returns to $v$.

• Compilation Build Systems: Make, Bazel, and Gradle model compilation targets as DAG nodes to orchestrate parallel builds.
• Version Control Systems (Git): Commits form a directed acyclic graph where child commits point backward to parent commits.
• Deep Learning Computation Engines: PyTorch autograd and TensorFlow represent tensor operations as directed acyclic computation graphs.

An undirected graph $G=(V,E)$ is Bipartite if its vertex set $V$ can be partitioned into two disjoint subsets $V_1$ and $V_2$ ($V_1\cup V_2=V$, $V_1\cap V_2=\varnothing$) such that every edge in $E$ connects a vertex in $V_1$ to a vertex in $V_2$. No edge connects two vertices within the same subset.

A graph is bipartite if and only if it contains no odd-length cycles.

Consider verifying whether graph with edges $\{(1,2),(2,3),(3,4),(4,1),(2,4)\}$ is bipartite.

export function isBipartite(n: number, adj: number[][]): boolean {
  const color = new Array(n + 1).fill(0); // 0 = unvisited, 1 = Red, -1 = Blue

  for (let start = 1; start <= n; start++) {
    if (color[start] !== 0) continue;

    const queue: number[] = [start];
    color[start] = 1;

    while (queue.length > 0) {
      const u = queue.shift()!;
      for (const v of adj[u]) {
        if (color[v] === 0) {
          color[v] = -color[u]; // Invert color for neighbor
          queue.push(v);
        } else if (color[v] === color[u]) {
          return false; // Odd cycle detected!
        }
      }
    }
  }

  return true;
}

1. Self-Loops and Handshaking:
   • A self-loop $(u,u)$ in an undirected graph contributes $+2$ to $\mathrm{deg}(u)$, as both endpoints attach to the same vertex. Neglecting this invalidates the Handshaking Lemma.
2. Disconnected Components in Traversal:
   • Graph algorithms (BFS, DFS, Bipartiteness) must loop through all vertices $1\dots V$ as potential search roots. Running BFS from a single vertex will fail to visit disconnected components.
3. Eulerian Path vs. Eulerian Circuit:
   • An Eulerian Circuit requires all vertices to have even degrees. An Eulerian Path requires exactly two vertices to have odd degrees (start and finish).

1. Euler, L. (1736). Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Scientiarum Petropolitanae, 8, 128–140.
2. Kőnig, D. (1936). Theorie der endlichen und unendlichen Graphen. Akademische Verlagsgesellschaft.
3. Kuratowski, K. (1930). Sur le problème des courbes gauches en topologie. Fundamenta Mathematicae, 15(1), 271–283.
4. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.), Chapter 20. MIT Press.