Math AI HL: Graph Theory Fundamentals

Graph theory is not just an abstract branch of mathematics; it is the essential language for modeling connections. Whether you're optimizing a delivery route, securing a computer network, or understanding the spread of information online, the ability to represent and analyze networks is a powerful tool. For IB Math AI HL, mastering these fundamentals provides a critical framework for solving complex, interconnected problems in technology, business, and science.

Graphs and Their Language

At its core, a graph is a set of objects and the connections between them. Formally, a graph $G$ is defined by two sets: a set $V$ of vertices (or nodes), and a set $E$ of edges (or arcs), where each edge connects a pair of vertices. This simple structure is deceptively powerful. For instance, vertices could represent cities, and edges could represent highways connecting them.

Graphs are classified by their edges. A simple graph has no loops (edges connecting a vertex to itself) and no more than one edge between any two vertices. When edges have a direction (like one-way streets), the graph is a digraph. If edges have assigned numerical values (like distances or costs), it is a weighted graph. Understanding this vocabulary is the first step in translating a messy real-world scenario into a clean, analyzable mathematical model.

The Power of Degree

The degree of a vertex is the number of edges incident to it. In a simple graph, you find it by counting connections. For a digraph, we distinguish indegree (edges coming in) and outdegree (edges going out). A fundamental theorem, the Handshaking Lemma, states that the sum of the degrees of all vertices in a graph is equal to twice the number of edges: $\sum \text{deg}(v)=2|E|$. This implies a simple but crucial fact: the number of vertices with an odd degree is always even.

Why does degree matter? It immediately tells you about the vertex's importance or connectivity in the network. A vertex with a high degree in a social network might be an influencer; a router with a high degree in a communication network is a critical hub. Analyzing degree distribution is often the first step in understanding any network's structure and resilience.

Euler’s Paths and Circuits

An Euler path is a trail that visits every edge of a graph exactly once. An Euler circuit is an Euler path that starts and ends at the same vertex. The existence of these paths is determined solely by vertex degrees, a beautiful result from Euler's solution to the Königsberg Bridge Problem.

For a connected graph:

• An Euler circuit exists if and only if every vertex has an even degree.
• An Euler path exists (but not a circuit) if and only if exactly two vertices have an odd degree. The path must start at one odd-degree vertex and end at the other.

Consider a graph modeling a postal worker's route. An Euler circuit would allow them to traverse every street once and return to the depot without retracing steps—the most efficient route for edge coverage. You don't check every possible path; you simply check the parity (even/odd) of all degrees.

Hamiltonian Paths and Circuits

In contrast, a Hamiltonian path visits every vertex exactly once, and a Hamiltonian circuit (or cycle) is a Hamiltonian path that returns to the start. This seems similar to the Eulerian problem but is fundamentally different and, in fact, computationally much harder. There is no simple known necessary and sufficient condition based on degree alone.

Instead, we work with sufficient conditions and algorithms. Dirac’s Theorem states that if a simple graph has $n$ vertices ($n\ge 3$) and every vertex has a degree of at least $n/2$, then the graph contains a Hamiltonian circuit. This is a guarantee, but not a requirement; many graphs with lower degrees still have Hamiltonian circuits. Finding such a circuit is like the classic "Traveling Salesperson Problem" — planning a tour to visit a set of cities once with minimal travel distance. Unlike checking for an Euler circuit, determining if a Hamiltonian circuit exists often requires systematic searching or clever deduction.

Modeling the Real World

Graph theory's true power lies in its applications. In transport networks, vertices are stations or intersections, and edges are routes. Finding the shortest path is a weighted graph problem, while designing a garbage collection route is an Euler circuit problem (if possible). In communication systems, graphs model how devices (routers, phones) are linked. Analyzing connectivity ensures network reliability; if a vertex (a central server) is removed, does the graph remain connected? This is the study of cut vertices and bridges.

Social networks are naturally modeled as graphs, where people are vertices and friendships are edges. The degree is the number of friends. Concepts like "cliques" (complete subgraphs where everyone is connected) and "connectivity" help analyze community structure and information flow. The "six degrees of separation" idea is fundamentally a statement about the diameter and average path length in the global social graph.

Common Pitfalls

1. Confusing Euler and Hamiltonian: The most frequent error is mixing up the conditions. Remember: Euler = every edge, condition on degree. Hamiltonian = every vertex, no simple degree rule. A quick mnemonic: "Euler Edges, Even Edges."
2. Misapplying Theorems: Dirac’s Theorem provides a sufficient, not necessary, condition for a Hamiltonian circuit. A graph not meeting Dirac's condition may still have a Hamiltonian circuit. Conversely, meeting the even-degree condition guarantees an Euler circuit only if the graph is connected—always check connectivity first.
3. Overlooking Graph Type: Applying simple graph theorems to digraphs or multigraphs (graphs with multiple edges) will lead to mistakes. For example, in a digraph, you must check indegree and outdegree for Eulerian trails, not just total degree.
4. Incorrect Degree Calculation in Non-Simple Graphs: In a graph with loops, remember that a loop contributes 2 to the degree of its vertex. This is essential for correctly applying the Handshaking Lemma and Euler's conditions.

Summary

• A graph is a model of connections consisting of vertices (nodes) and edges (links). Key classifications include simple graphs, digraphs, and weighted graphs.
• The degree of a vertex counts its connections. The Handshaking Lemma ($\sum \text{deg}(v)=2|E|$) is a fundamental property, and vertices of odd degree always appear in pairs.
• Euler paths/circuits traverse every edge once. Their existence is neatly determined by vertex degrees: all even for a circuit, exactly two odd for a path (in a connected graph).
• Hamiltonian paths/circuits visit every vertex once. No simple degree-based rule exists, though theorems like Dirac’s provide sufficient conditions for a circuit's existence.
• Graph theory is indispensable for modeling real-world networks, from optimizing transport routes and securing communications to analyzing social connections and the flow of influence or disease.