Mathematical Foundations: Graph Theory and Network Representation

The study of complex systems—whether social, biological, technological, or informational—fundamentally relies on the ability to represent and analyze relationships between entities. A social network connects individuals through friendships, collaborations, or communication patterns; a citation network links academic works through references; a transportation network ties locations via routes and connections. The mathematical abstraction that captures these relational structures is the *graph*, and the systematic study of graphs constitutes the field of *graph theory*. This chapter establishes the rigorous mathematical foundation necessary for understanding network science, presenting graph-theoretic concepts in a manner that bridges theoretical elegance with practical engineering concerns.

The importance of graph theory to network science extends far beyond mere definitional convenience. Graphs provide a unified language for describing diverse systems, allowing techniques from linear algebra, combinatorics, and probability theory to inform our understanding of network behavior. Moreover, the properties of graphs directly determine algorithmic approaches for network analysis, from simple neighbor enumeration to sophisticated spectral methods. Understanding the mathematical structure of networks enables practitioners to make informed decisions about representation choices, algorithm selection, and computational strategy—decisions that profoundly affect the tractability and accuracy of network analysis at scale.

Formal Foundations: Graphs, Vertices, and Edges

Basic Definitions

A graph $G = (V, E)$ consists of a finite set of vertices (also called nodes or points) $V$ and a finite set of edges (also called links, ties, or connections) $E$. Each edge is an unordered pair $\{u, v\}$ of distinct vertices, representing a relationship between these vertices. This fundamental definition, while simple, admits rich structure and numerous variations that we shall explore throughout this chapter.

The order of a graph is the number of vertices, denoted $|V| = n$, while the size of a graph is the number of edges, denoted $|E| = m$. These fundamental quantities appear repeatedly in network analysis, from density calculations to computational complexity arguments. For a graph of order $n$, the maximum possible number of edges in an undirected graph is $\binom{n}{2} = n(n-1)/2$, a bound that proves essential when discussing network sparsity.

A vertex $v \in V$ has a neighborhood $N(v) = \{u \in V : \{u, v\} \in E\}$, the set of vertices directly connected to $v$. The degree of a vertex, denoted $\deg(v) = |N(v)|$, counts these connections. The degree sequence $\mathcal{D} = (\deg(v_1), \deg(v_2), \ldots, \deg(v_n))$ provides a compact summary of local connectivity patterns. The Handshaking Lemma, a fundamental result in graph theory, establishes that

$$\sum_{v \in V} \deg(v) = 2|E|$$

since each edge contributes exactly two to the total degree count. This simple identity has profound implications, including the fact that the number of odd-degree vertices must be even.

Example 1.1: Co-authorship Network Representation

Consider a co-authorship network constructed from academic publications. Each vertex represents a researcher, and an edge connects two vertices if the corresponding researchers have co-authored at least one paper. In this representation, the degree of a vertex equals the number of distinct co-authors a researcher has worked with. The famous mathematician Paul Erdős, who authored papers with an extraordinary number of collaborators, would have an exceptionally high degree in such a network. The Erdős–Rényi model of random graphs, which we shall discuss extensively in subsequent chapters, was partially motivated by analyzing such collaboration patterns.

The properties of this graph reveal important characteristics of scientific collaboration. Highly connected vertices may represent prolific researchers or leaders of large research groups. The existence of bridges between different research communities indicates interdisciplinary collaboration. The graph's structure can inform strategies for literature review, identifying key researchers whose work spans multiple subfields.

Path-Based Structures

Beyond basic connectivity, the structure of paths within a graph reveals essential properties of the network. A path of length $k$ is a sequence of distinct vertices $v_0, v_1, \ldots, v_k$ where each consecutive pair $\{v_{i-1}, v_i\} \in E$. The distance between two vertices, denoted $d(u, v)$, is the length of the shortest path connecting them. A graph is connected if a path exists between every pair of vertices; otherwise, it consists of multiple connected components.

The diameter of a connected graph is the maximum distance between any pair of vertices:

$$\text{diam}(G) = \max_{u,v \in V} d(u, v)$$

This quantity measures the "span" of the network. Many real-world networks exhibit the small-world property: despite having thousands or millions of vertices, their diameter remains surprisingly small—often logarithmic in the number of vertices rather than linear.

A cycle is a path that returns to its starting vertex without repetition, forming a closed loop. Cycles are fundamental to understanding network resilience: the removal of edges on cycles can often be compensated by alternative routes, while edges not belonging to any cycle represent critical bridges whose removal disconnects the network.

A tree is a connected graph with exactly $n-1$ edges and no cycles. Trees represent the most efficient connected structures, having minimal edge count while maintaining connectivity. Any connected graph contains a spanning tree—a subgraph that is a tree and includes all vertices—as a backbone structure. The enumeration and properties of spanning trees relate to network reliability and flow optimization.

Walks, Trails, and Closed Walks

While paths require vertex distinctness, related concepts relax this constraint. A walk is a sequence of vertices where consecutive vertices are adjacent, with no restrictions on repetition. A trail is a walk with no repeated edges. The length of walks connects to fundamental spectral properties through the adjacency matrix, as we shall see in subsequent sections.

The girth of a graph is the length of its shortest cycle, while the circumference is the length of its longest cycle. These quantities constrain the possible spectral properties and algorithmic approaches applicable to the graph. Graphs with large girth can be constructed to have specific spectral properties, a fact exploited in expander graph constructions.

Matrix Representations of Network Structure

The algebraic representation of graphs through matrices enables the application of linear algebraic techniques to network analysis. Three matrices prove particularly important: the adjacency matrix, the incidence matrix, and the Laplacian matrix.

The Adjacency Matrix

For a graph $G = (V, E)$ with vertices indexed $1, 2, \ldots, n$, the adjacency matrix $A \in \mathbb{R}^{n \times n}$ is defined as:

$$A_{ij} = \begin{cases} 1 & \text{if } \{i, j\} \in E \\ 0 & \text{otherwise} \end{cases}$$

For an undirected graph, $A$ is symmetric: $A = A^T$. This symmetry implies real eigenvalues and orthogonal eigenvectors, properties that prove computationally and theoretically valuable.

The adjacency matrix encodes paths of arbitrary length through matrix multiplication. Specifically, $(A^k)_{ij}$ equals the number of distinct walks of length $k$ from vertex $i$ to vertex $j$. This observation connects combinatorial path-counting to linear algebraic computation:

$$(A^2)_{ii} = \sum_{j=1}^n A_{ij} A_{ji} = \sum_{j=1}^n A_{ij}^2 = \deg(i)$$

More generally, the number of walks of length $k$ from $i$ to $j$ grows like $\lambda_j^k$ where $\lambda_j$ are the eige