Core Foundations of Graph Theory

Introduction to Graph Theory: Fundamental Concepts and Definitions What is a Graph? Graph theory is the branch of mathematics that studies graphs—structures that model pairwise relationships between objects. A graph consists of a collection of objects (called vertices) connected by relationships (called edges). This simple but powerful framework appears everywhere: in social networks where vertices are people and edges represent friendships, in transportation networks where vertices are cities and edges are roads, and in countless other real-world systems. The key insight of graph theory is that by abstracting away the specific details of what the vertices and edges represent, we can discover universal principles that apply across all these domains. Undirected Simple Graphs The simplest type of graph is an undirected simple graph. Formally, it's an ordered pair $(V, E)$ where: $V$ is a non-empty finite set of vertices (also called nodes) $E$ is a set of edges, where each edge is an unordered pair $\{u, v\}$ of distinct vertices The term "unordered pair" is important: it means the edge $\{u, v\}$ is the same as the edge $\{v, u\}$. There's no direction to the edge. The term "simple" means there are no multiple edges between the same pair of vertices, and no loops. Example: If $V = \{1, 2, 3, 4\}$ and $E = \{\{1,2\}, \{2,3\}, \{3,4\}, \{1,4\}\}$, then we have a simple graph with 4 vertices and 4 edges forming a square-like structure. Multigraphs and Multiple Edges Real-world applications sometimes require multiple edges between the same pair of vertices. For example, two cities might be connected by several different highways. This leads us to the definition of an undirected multigraph, which is an ordered triple $(V, E, \mu)$ where: $V$ is a set of vertices $E$ is a set of edges (now just abstract objects, not pairs of vertices) $\mu: E \to \{\{u,v\} \mid u, v \in V\}$ is a function that assigns each edge to a pair of vertices The function $\mu$ is what makes multigraphs different from simple graphs. It allows multiple distinct edges (in set $E$) to be assigned to the same pair of vertices. So while a simple graph can have at most one edge between vertices $u$ and $v$, a multigraph can have many. Why does this matter? In simple graphs, we can denote an edge by just saying which two vertices it connects. In multigraphs, edges are distinct objects that we need to track separately, even if they connect the same pair of vertices. Loops and Pseudographs A loop is an edge that connects a vertex to itself—that is, both endpoints are the same vertex. In a simple graph, loops are not allowed. A pseudograph is a more general graph type that permits both multiple edges and loops. Formally, a pseudograph is a multigraph where $\mu$ can map edges to pairs $\{u, u\}$. Practical example: In modeling electrical circuits or chemical bonding, loops can represent self-connections that are meaningful in those contexts. Directed Graphs (Digraphs) So far, all our edges have been undirected—they represent symmetric relationships. But many real situations have asymmetric relationships: a person might follow another on social media without being followed back; a river flows in one direction; a hyperlink goes from one web page to another. A directed simple graph (or digraph) is an ordered pair $(V, A)$ where: $V$ is a set of vertices $A \subseteq V \times V$ is a set of arcs (directed edges), represented as ordered pairs $(u, v)$ For an arc $(u, v)$: $u$ is called the tail (starting point) $v$ is called the head (ending point) Crucially, $(u, v)$ and $(v, u)$ are different arcs. The arc goes from $u$ to $v$, not the other way around. Key difference: In undirected graphs, we write edges as unordered pairs $\{u, v\}$. In directed graphs, we write arcs as ordered pairs $(u, v)$. Directed Multigraphs (Quivers) Just as we extended simple undirected graphs to multigraphs, we can extend digraphs to allow multiple arcs between the same pair of vertices. A directed multigraph (also called a quiver in some contexts) is an ordered triple $(V, A, \mu)$ where: $V$ is a set of vertices $A$ is a set of arcs $\mu: A \to V \times V$ assigns each arc to an ordered pair of vertices Loops are permitted: an arc can have the form $(v, v)$. <extrainfo> The term "quiver" comes from representation theory and category theory, where directed multigraphs are used to encode algebraic structures. This specialized terminology may not appear on a basic graph theory exam. </extrainfo> Order, Size, and Degree When working with graphs, we need to measure their basic properties: Order is the number of vertices: $|V|$. A graph of order 5 has 5 vertices. Size is the number of edges (or arcs in directed graphs): $|E|$ or $|A|$. A graph of size 3 has 3 edges. Degree of a vertex is the count of edges incident to it. For a vertex $v$, we write this as $\deg(v)$. Here's an important detail: in the degree count, each loop contributes 2 to the degree of its vertex. This might seem odd, but it's by design. The reasoning is that a loop connects a vertex to itself, so it creates a kind of "double contribution" that we count as 2. This convention ensures that important theorems work out nicely (like the handshaking lemma, which states that the sum of all degrees equals twice the number of edges). Example: If vertex $v$ has 3 regular edges connecting it to other vertices and 1 loop, then $\deg(v) = 3 + 2 = 5$. The Complete Graph Among all simple graphs of a given order, there is one with the maximum number of edges: the complete graph $Kn$ on $n$ vertices. In $Kn$, every pair of distinct vertices is connected by exactly one edge. The maximum number of edges in a simple undirected graph of order $n$ is: $$\frac{n(n-1)}{2}$$ This formula comes from counting: there are $\binom{n}{2}$ ways to choose 2 vertices from $n$ vertices, and each choice corresponds to exactly one edge in a complete graph. Example: $K4$ (complete graph on 4 vertices) has $\frac{4 \cdot 3}{2} = 6$ edges. Every vertex in $K4$ has degree 3. Bipartite Graphs A bipartite graph is an undirected graph whose vertex set $V$ can be partitioned into two disjoint subsets $U$ and $W$ (so $V = U \cup W$ and $U \cap W = \emptyset$) such that every edge connects a vertex in $U$ to a vertex in $W$. No edges exist within $U$ or within $W$. Intuition: Think of the vertices as divided into two teams, and edges can only go between teams, not within teams. Why is this important? Bipartite graphs model many practical situations: job applicants and job positions, students and courses, left and right sides of a matching problem. Many important problems in computer science and optimization involve bipartite graphs. Example: A graph with vertices $U = \{a, b\}$ and $W = \{1, 2, 3\}$ where edges connect $a$ to $\{1, 2\}$ and $b$ to $\{2, 3\}$ is bipartite. There are edges between different sets but never within $U$ or within $W$. <extrainfo> Historical Notes Graph theory has a rich history. The mathematical study of graphs began with Arthur Cayley's work on trees in 1857, formalized in his paper "On the theory of the analytical forms called trees." Cayley later extended tree theory to chemistry, recognizing that the structure of chemical compounds could be represented as tree-like graphs. The comprehensive modern treatment of graph theory is largely due to William Thomas Tutte, whose textbook "Graph Theory" (2001) standardized much of the terminology and theory we use today. While understanding this history provides helpful context, the historical facts themselves are unlikely to be tested on exams focused on graph theory fundamentals. </extrainfo>