What Is Graph Theory: Nodes, Edges, and How Networks Are Analyzed

Graphs as a Mathematical Language

Graph theory is a branch of mathematics concerned with networks of objects and the connections between them. In the mathematical sense, a graph is not a chart or a plot but a structure consisting of vertices (also called nodes) and edges (also called links or arcs) that connect pairs of vertices. This simple framework — points and lines — turns out to be extraordinarily versatile, capable of representing anything from social friendships and airline routes to protein interactions and the links between web pages.

The discipline was born in 1736 when Swiss mathematician Leonhard Euler solved the Seven Bridges of Königsberg problem. The city of Königsberg (now Kaliningrad, Russia) was built on islands connected by seven bridges, and residents wondered whether it was possible to walk through the city crossing each bridge exactly once. Euler proved it was impossible, not by trial and error but by abstracting the problem: representing land masses as nodes and bridges as edges and proving that such a path (now called an Eulerian path) requires all or exactly two nodes to have an odd number of connections. This elegant solution inaugurated a mathematical language for reasoning about networks that has grown into one of the most practically important fields in modern science.

Types of Graphs and Their Properties

Mathematical graphs come in several varieties, each suited to different modeling situations. An undirected graph treats connections symmetrically — if node A connects to node B, the connection goes both ways, as in a friendship network. A directed graph (digraph) assigns direction to edges — one-way streets, follower relationships on Twitter, and web hyperlinks are naturally directed. A weighted graph assigns numerical values to edges representing distance, cost, capacity, or strength — essential for routing problems and optimization.

Several graph properties are particularly important for analysis. The degree of a vertex is the number of edges connected to it — in directed graphs, this splits into in-degree and out-degree. A path is a sequence of vertices where each consecutive pair is connected by an edge; a cycle is a path that returns to its starting vertex. A connected graph has a path between every pair of vertices, while a disconnected graph has isolated components. A tree is a connected graph with no cycles — trees have exactly n-1 edges for n vertices and are fundamental to computer science data structures and algorithms.

Special classes of graphs arise in applications. Bipartite graphs have vertices split into two groups with edges only between groups — useful for modeling matching problems like assigning workers to jobs. Complete graphs connect every vertex to every other. Planar graphs can be drawn on a flat surface without edges crossing — road networks are approximately planar. Random graphs, studied by Erdős and Rényi in the 1950s and 60s, have edges added probabilistically and exhibit phase transitions that model real-world network phenomena.

Fundamental Algorithms in Graph Theory

Some of the most important algorithms in computer science are graph algorithms. Breadth-first search (BFS) and depth-first search (DFS) are fundamental traversal strategies: BFS explores all neighbors of a vertex before moving to the next level, making it optimal for finding shortest paths in unweighted graphs; DFS dives as deep as possible along each branch before backtracking, useful for detecting cycles and topological sorting. Dijkstra's algorithm, published in 1959, finds the shortest weighted path from a source vertex to all other vertices in a graph with non-negative edge weights — the foundation of GPS navigation and network routing protocols.

Minimum spanning tree algorithms — Prim's and Kruskal's — find the subset of edges that connects all vertices with minimum total weight, used in network design to minimize cable or road infrastructure costs. Maximum flow algorithms, particularly the Ford-Fulkerson method, find the maximum amount of flow through a network from a source to a sink — modeling traffic, fluid dynamics, and bandwidth allocation. The traveling salesman problem (TSP) — finding the shortest route visiting all vertices and returning to the start — is one of the most famous NP-hard problems, meaning no efficient exact algorithm is known for large instances, driving research into approximation algorithms and heuristics.

Network Science: Real-World Graph Structure

The late 1990s and early 2000s saw an explosion of interest in the structure of real-world networks — the internet, social networks, biological networks, power grids, and citation networks — sparked by foundational work from physicists and sociologists. Two properties emerged as nearly universal in complex networks: small-world structure and scale-free degree distributions.

Small-world networks, characterized by Stanley Milgram's famous 1967 experiment (the origin of "six degrees of separation"), combine high local clustering — friends of friends are likely friends — with short average path lengths between any two nodes. The Watts-Strogatz model showed that even adding a small number of long-range connections to a clustered network dramatically reduces average path length, explaining why information spreads so rapidly through social networks. Scale-free networks, identified by Barabási and Albert in 1999, have degree distributions following a power law: most nodes have few connections, but a small number of hubs have enormously many. This pattern — observed in the web, citation networks, protein interaction networks, and air travel — arises from preferential attachment, where new nodes preferentially connect to already well-connected nodes ("the rich get richer").

Applications Across Science and Technology

Graph theory permeates modern technology and science. The World Wide Web is a directed graph of web pages and hyperlinks; Google's PageRank algorithm ranks pages based on the structure of this graph, with pages receiving more link-weight from highly linked pages. Social networks like Facebook and LinkedIn are analyzed with graph theory to identify communities, influential nodes, and information propagation patterns. Epidemiologists use network models to predict how diseases spread through contact networks — a lesson reinforced by COVID-19 research that used contact tracing data to parameterize graph-based transmission models.

In biology, protein-protein interaction networks, metabolic pathway graphs, and gene regulatory networks are analyzed to understand cellular function and identify drug targets. Graph neural networks — a powerful machine learning architecture — operate directly on graph-structured data and have achieved state-of-the-art results in drug discovery, materials science, and social recommendation systems. In logistics, vehicle routing problems (VRPs) — determining optimal delivery routes for fleets of vehicles — are graph optimization problems with billions of dollars of annual economic impact. Compiler design, circuit routing in integrated circuits, and scheduling problems are all graph problems in disguise. Few areas of applied mathematics have found more diverse and consequential applications than graph theory.

Unsolved Problems and Frontiers

Graph theory contains some of mathematics' most famous unsolved problems. The Four Color Theorem — that any planar map can be colored with four colors such that no adjacent regions share a color — was proved in 1976 by Appel and Haken using computer-assisted case analysis, becoming the first major mathematical theorem proved with substantial computer aid, and sparking debate about what constitutes a valid mathematical proof. The Ramsey theory problem of determining Ramsey numbers R(k, l) — the minimum graph size guaranteeing a clique of size k or an independent set of size l — remains open for most values beyond small cases.

Graph isomorphism — determining whether two graphs are structurally identical up to relabeling of vertices — occupies a unique position in computational complexity, believed to be neither in P (polynomial time) nor NP-complete, though this has not been proved. Subgraph isomorphism, finding whether one graph contains another as a substructure, is NP-complete and has important applications in pattern recognition, drug design, and network analysis. The P versus NP question — whether all problems verifiable in polynomial time are also solvable in polynomial time — is intimately connected with many graph algorithm questions and remains the most important open problem in mathematics and theoretical computer science.