Discrete Mathematics: Graph Theory

Graph theory is the mathematical backbone of network science, providing the language and tools to model, analyze, and optimize systems of interconnected entities. From routing internet traffic and organizing logistics to understanding the spread of information in social media, graph theory transforms complex relational problems into precise, solvable models. Mastering its core principles empowers you to tackle challenges in computer science, operations research, sociology, and biology with a structured, analytical approach.

Fundamentals of Graphs and Terminology

A graph $G$ is a mathematical structure used to model pairwise relationships between objects. It is formally defined as an ordered pair $G=(V,E)$, where $V$ is a finite, non-empty set of vertices (or nodes), and $E$ is a set of edges (or links) connecting pairs of vertices. Each edge is associated with two vertices; if the edge is an unordered pair, the graph is undirected. If each edge is an ordered pair, indicating a direction from one vertex to another, the graph is directed (often called a digraph).

The degree of a vertex in an undirected graph is the number of edges incident to it. In a directed graph, we distinguish in-degree (edges coming in) and out-degree (edges going out). These simple metrics are the first step in analyzing a network's structure. For instance, in a social network graph where vertices represent people and edges represent friendships, a vertex with a high degree is a highly connected individual, potentially an influencer.

Graphs can be represented in several ways, each useful for different computational tasks. The adjacency matrix is a square matrix where entry $a_{ij}$ is 1 (or a weight) if there is an edge from vertex $i$ to vertex $j$, and 0 otherwise. The adjacency list stores, for each vertex, a list of the vertices it is connected to. The matrix representation allows for fast edge lookup, while the list representation is more space-efficient for sparse graphs (graphs with relatively few edges compared to the maximum possible).

Connectivity, Paths, and Special Graph Structures

Connectivity defines how easily one can traverse a graph. A path is a sequence of vertices where each adjacent pair is connected by an edge, with no vertex repeated (except possibly the first and last). A cycle is a path that starts and ends at the same vertex. A graph is connected if there is a path between every pair of vertices. In directed graphs, if there is a directed path from any vertex to any other vertex, the graph is strongly connected.

Detecting paths and cycles is fundamental. A simple path visits no vertex twice, while a simple cycle is a cycle that does not repeat vertices or edges (other than the start/end vertex). Algorithms for path detection, like Depth-First Search (DFS), explore as far as possible along a branch before backtracking, making them ideal for uncovering complex connections and cycles.

Several special graph types form the building blocks of the theory. A tree is a connected, undirected graph with no cycles. Trees have exactly $|V|-1$ edges and have the property that there is exactly one simple path between any two vertices. They are hierarchical structures essential for data organization (like binary search trees) and network design. A complete graph $K_n$ has an edge between every pair of its $n$ vertices. A bipartite graph is one whose vertices can be divided into two disjoint sets, $U$ and $V$, such that every edge connects a vertex in $U$ to one in $V$. This model perfectly represents relationships between two different classes of objects, such as job applicants and open positions.

Graph Algorithms and Applied Problem Solving

Graph theory shines in its algorithmic applications for solving optimization problems. Two famous historical problems illustrate key concepts. An Euler path is a path that traverses every edge of a graph exactly once. An Euler circuit is an Euler path that starts and ends at the same vertex. Euler's Theorem provides a clean criterion: a connected graph has an Euler circuit if and only if every vertex has an even degree. This solves the "Königsberg bridge problem" and has applications in garbage collection routing and circuit design. A Hamilton path is a path that visits every vertex exactly once, and a Hamilton cycle is a Hamilton path that is a cycle. Unlike Euler's, no known efficient general criterion exists for detecting Hamilton paths, making it a classic NP-complete problem relevant to the traveling salesperson problem.

Finding the shortest path between two vertices is a critical task in networking and GPS navigation. Dijkstra's algorithm is the most famous solution for graphs with non-negative edge weights. It works by iteratively selecting the unvisited vertex with the smallest known distance from the source, updating the distances to its neighbors, and marking it as visited. For a graph with $|V|$ vertices and $|E|$ edges, a well-implemented version using a priority queue runs in $O(|E|+|V|\log |V|)$ time.

When the goal is to connect all vertices in a network at minimum total cost without creating cycles, you need a minimum spanning tree (MST). Kruskal's algorithm builds the MST by sorting all edges by weight and adding them one by one, skipping any edge that would form a cycle, until the tree connects all vertices. Prim's algorithm grows the MST from an arbitrary starting vertex, always adding the cheapest edge that connects a vertex in the tree to a vertex not yet in the tree. Both algorithms are greedy and produce optimal results, with applications in designing cost-efficient computer, road, and utility networks.

Graph coloring assigns colors to vertices such that no two adjacent vertices share the same color. The smallest number of colors needed is the chromatic number $\chi (G)$. This is not just a puzzle; it models conflict resolution. For example, scheduling final exams so no student has two at the same time can be modeled as a graph coloring problem, where vertices are courses, edges connect courses with overlapping students, and colors represent time slots. The Four Color Theorem, a landmark result, states that any planar graph (one that can be drawn on a plane without edges crossing) has a chromatic number of at most four.

Common Pitfalls

1. Confusing Euler and Hamilton Paths: Students often conflate these concepts. Remember: Euler concerns edges (using each once), Hamilton concerns vertices (visiting each once). A useful mnemonic: "Euler Edges, Hamilton Houses (vertices)." Check Euler conditions using vertex degrees; for Hamilton, there is no simple test.
2. Misapplying Dijkstra's Algorithm with Negative Weights: Dijkstra's algorithm fails if edge weights can be negative. It relies on the assumption that once a vertex's shortest distance is finalized, it cannot be improved. Negative weights violate this. For graphs with potential negative weights, you must use the Bellman-Ford algorithm instead.
3. Assuming All Trees Are Binary: In graph theory, a tree is defined solely by being connected and acyclic. It can have vertices with any number of children (a general tree). Binary trees are a specific subtype with application in computer science, but the graph-theoretic definition is more general. Do not impose a "maximum two children" rule unless specified.
4. Overlooking Graph Representation Trade-offs: Choosing an adjacency matrix over a list (or vice versa) without considering the graph's density is a common error. For a sparse graph with 10,000 vertices and 20,000 edges, a $10,000\times 10,000$ adjacency matrix is hugely wasteful of space. Always analyze the expected number of edges $|E|$ relative to $|V{|}^2$ before selecting a representation.

Summary

• Graph theory formalizes the study of networks using vertices (nodes) and edges (connections), providing a universal model for relational data in fields from computer networking to social analysis.
• Core structures like paths, cycles, trees, and special graph types (complete, bipartite) establish the language for describing connectivity and hierarchical relationships within a system.
• Algorithmic problem-solving is central, with efficient methods like Dijkstra's algorithm for shortest paths and Kruskal's/Prim's algorithms for finding minimum spanning trees enabling optimization in logistics and design.
• Historical problems like the Euler and Hamilton paths illustrate the distinction between efficiently solvable problems and intractable ones, while graph coloring offers practical tools for resource allocation and scheduling conflicts.
• Understanding the assumptions and limitations of each theorem and algorithm—such as Dijkstra's incompatibility with negative weights or the non-existence of a simple test for Hamilton paths—is crucial for correct application.