Graph Theory: Networks of Nodes and Edges

In 1736, the people of Königsberg had a question.

Their city sat on the Pregel River, divided into four landmasses connected by seven bridges. The puzzle: Could you walk through the city crossing each bridge exactly once?

People tried. No one succeeded. But no one could prove it was impossible—until Leonhard Euler abstracted the problem.

He didn't care about the physical bridges or the shape of the landmasses. He reduced the city to points (nodes) and connections (edges). Four nodes, seven edges. Then he proved: If a graph has more than two nodes with an odd number of edges, no Eulerian path exists.

Königsberg had four nodes with odd degree. Therefore, impossible.

Euler didn't solve the problem by trying paths. He solved it by inventing graph theory—the mathematics that three centuries later would power Google Maps, Facebook's social network, the internet's routing protocols, and every recommendation algorithm you've ever seen.

What Is a Graph?

A graph is a collection of nodes (also called vertices) connected by edges (also called links or arcs).

That's it. Nodes and edges. Everything else is structure built on that foundation.

Examples:

• Cities and roads: Nodes = cities, edges = roads
• People and friendships: Nodes = people, edges = friendships (social network)
• Webpages and hyperlinks: Nodes = pages, edges = links (the internet)
• Neurons and synapses: Nodes = neurons, edges = connections (neural networks)
• Computers and connections: Nodes = devices, edges = network links (computer networks)

Graph theory is the mathematics of relationships. Whenever you have objects and connections between them, you have a graph.

Directed vs. Undirected Graphs

Undirected graph: Edges have no direction. If A connects to B, then B connects to A.

• Example: Friendship on Facebook (symmetric)

Directed graph (digraph): Edges have direction. A→B doesn't imply B→A.

• Example: Following on Twitter (asymmetric)
• Example: One-way streets

Weighted graph: Edges have values (weights).

• Example: Roads with distances, costs, or travel times

Unweighted graph: All edges are equivalent.

• Example: "Are these two people friends?" (yes/no, no degree of friendship)

Most real-world networks are directed and weighted. Graph theory handles all variations.

Key Graph Concepts

Degree

The degree of a node is the number of edges connected to it.

In directed graphs:

• In-degree: Number of incoming edges
• Out-degree: Number of outgoing edges

Example: On Twitter, your follower count is in-degree, following count is out-degree.

Path

A path is a sequence of nodes where each adjacent pair is connected by an edge.

Example: In a road network, a path is a route from city A to city B.

Cycle

A cycle is a path that starts and ends at the same node.

Example: A loop in a road network that brings you back to where you started.

Connected Graph

A graph is connected if there's a path between every pair of nodes.

Example: The internet is (mostly) connected—you can reach any website from any other via routing.

Complete Graph

A complete graph has an edge between every pair of nodes.

For n nodes, a complete graph has C(n, 2) = n(n-1)/2 edges.

Example: A round-robin tournament where every player plays every other player.

The Handshake Lemma

Theorem: The sum of all node degrees equals twice the number of edges.

Σ deg(v) = 2|E|

Why? Each edge contributes 1 to the degree of each of its two endpoints. So each edge is counted twice in the sum of degrees.

Corollary: Every graph has an even number of nodes with odd degree.

Why? If the sum of degrees is even (it's 2|E|), and you're adding up a bunch of numbers, an odd number of odd-degree nodes would make the sum odd. Contradiction.

This seems trivial, but it's the proof of why Königsberg's bridges can't be crossed. More than two odd-degree nodes means no Eulerian path exists.

Eulerian Paths and Circuits

An Eulerian path traverses every edge exactly once.

An Eulerian circuit is an Eulerian path that returns to the starting node.

Euler's Theorem:

• A connected graph has an Eulerian circuit if and only if every node has even degree.
• A connected graph has an Eulerian path (but not circuit) if and only if exactly two nodes have odd degree.

Why this matters:

• Route planning: Postal workers, garbage collection—minimize backtracking.
• DNA sequencing: Reassembling genome fragments (treating sequences as edges).
• Network inspection: Checking all connections without redundancy.

Google Maps doesn't just find the shortest path—it solves variants of Eulerian path problems for efficient routing.

Hamiltonian Paths: The Harder Problem

A Hamiltonian path visits every node exactly once (edges can repeat).

A Hamiltonian circuit is a Hamiltonian path that returns to the start.

Unlike Eulerian paths, there's no simple test for Hamiltonian paths. No known polynomial-time algorithm determines whether a Hamiltonian path exists. This is NP-complete.

The Traveling Salesman Problem (TSP): Given n cities and distances, find the shortest Hamiltonian circuit.

This is one of the most famous NP-hard problems. For small n, brute force works (try all (n-1)!/2 routes). For large n, it's intractable. Approximation algorithms and heuristics are used instead.

TSP appears in logistics, circuit board drilling, genome sequencing, and anywhere you need to optimize a route visiting all locations.

Graph Coloring

Graph coloring: Assign colors to nodes such that no two adjacent nodes share the same color. Use the minimum number of colors.

The chromatic number is the minimum colors needed.

Applications:

• Scheduling: If two events conflict (share an edge), they need different time slots (colors). Chromatic number = minimum time slots needed.
• Register allocation: In compilers, variables that are "live" simultaneously can't share the same register. Model as graph coloring.
• Map coloring: Adjacent countries need different colors. The famous Four Color Theorem states any map can be colored with at most 4 colors. Proved in 1976 using computer verification—controversial at the time.

Graph coloring is NP-hard for general graphs, but polynomial for certain types (bipartite graphs, planar graphs).

Bipartite Graphs

A graph is bipartite if nodes can be divided into two sets such that all edges connect nodes from different sets (no edges within a set).

Example: Dating app matching—users on one side, potential matches on the other. Edges represent compatibility.

Theorem: A graph is bipartite if and only if it contains no odd-length cycles.

Applications:

• Matching problems: Assigning workers to jobs, students to schools, organs to transplant recipients.
• Stable marriage problem: Pair n men and n women such that no pair prefers each other over their assigned partners. Gale-Shapley algorithm solves this in O(n²) time.

Shortest Path Algorithms

Finding the shortest path between two nodes is fundamental.

Breadth-First Search (BFS)

For unweighted graphs, BFS finds the shortest path in O(V + E) time.

How it works: Explore neighbors level-by-level. First node reached is the shortest path (minimum edges).

Dijkstra's Algorithm

For weighted graphs with non-negative weights, Dijkstra's algorithm finds shortest paths from a source node to all others in O(E log V) time (with a priority queue).

How it works: Greedily expand the closest unvisited node, updating distances to neighbors.

Applications: GPS routing, network packet routing, social network influence.

Bellman-Ford Algorithm

Handles negative edge weights (Dijkstra fails here). Runs in O(VE) time.

Why negative weights matter: Currency arbitrage, network flow with costs/gains.

A* Search

Heuristic-guided Dijkstra. Uses estimated distance to goal to prioritize exploration. Faster in practice for specific targets.

Applications: Game pathfinding, robotics, map routing.

Minimum Spanning Trees

A spanning tree of a graph is a subgraph that connects all nodes with no cycles.

A minimum spanning tree (MST) is a spanning tree with minimum total edge weight.

Kruskal's Algorithm

Sort edges by weight. Add edges one by one, skipping any that form a cycle. O(E log E) time.

Prim's Algorithm

Start from a node. Repeatedly add the cheapest edge connecting the tree to a new node. O(E log V) time.

Applications:

• Network design: Minimize cable length connecting all locations.
• Clustering: MST-based clustering in machine learning.
• Image segmentation: Treat pixels as nodes, edge weights as dissimilarity.

Centrality: Who's Important?

In a network, which nodes are most influential?

Degree Centrality

Simply the degree (number of connections). High-degree nodes are "hubs."

Problem: Doesn't account for the importance of neighbors.

Betweenness Centrality

Measures how often a node lies on shortest paths between other nodes. High betweenness = bridge/gatekeeper.

Example: Airports like Atlanta hub connecting many routes.

Closeness Centrality

Average distance to all other nodes. Low closeness = central position in network.

Eigenvector Centrality

Importance based on having important neighbors. Recursive definition.

PageRank (Google's algorithm) is a variant: a page is important if important pages link to it.

Centrality measures identify influencers, critical infrastructure, vulnerabilities in networks.

Small-World Networks

Real-world networks often exhibit small-world properties:

• High clustering: Friends of friends tend to be friends (triangles).
• Short average path length: "Six degrees of separation"—any two people connected by ~6 steps.

Watts-Strogatz model generates small-world networks: start with a regular lattice, randomly rewire a few edges. Boom—short paths emerge while clustering remains high.

Examples: Social networks, neural networks, power grids, the internet.

Small-world structure makes networks robust to random failures but vulnerable to targeted attacks on hubs.

Scale-Free Networks

Many real networks are scale-free: degree distribution follows a power law. Most nodes have few connections, a few have many (hubs).

Barabási–Albert model: Networks grow via preferential attachment—new nodes connect to existing nodes proportional to their degree. "The rich get richer."

Examples: Internet topology, citation networks, social networks, protein interaction networks.

Implications:

• Robustness: Random node removal barely affects connectivity (you usually hit low-degree nodes).
• Vulnerability: Targeted removal of hubs fragments the network.
• Disease spread: Hubs are super-spreaders. Remove them, you control epidemics.

Network Flows

Max-flow problem: Given a network with capacities on edges, find the maximum flow from source to sink.

Min-cut problem: Find the minimum capacity cut separating source and sink.

Max-flow min-cut theorem: Maximum flow = minimum cut capacity.

Ford-Fulkerson algorithm computes max flow by finding augmenting paths.

Applications:

• Traffic networks: Maximum cars through a road system.
• Supply chains: Optimize flow of goods.
• Image segmentation: Treat pixels as nodes, cut to segment objects.
• Network security: Identify bottlenecks and vulnerabilities.

Community Detection

Real networks have communities—densely connected subgraphs with sparse connections between them.

Algorithms:

• Girvan-Newman: Remove edges with highest betweenness, revealing communities.
• Modularity maximization: Optimize a metric comparing actual vs. expected edges within communities.
• Louvain method: Fast hierarchical clustering.

Applications:

• Social networks: Detect friend groups, echo chambers.
• Biology: Identify functional modules in protein networks.
• Marketing: Customer segmentation.

Planar Graphs

A planar graph can be drawn in the plane without edge crossings.

Euler's formula for planar graphs: V - E + F = 2

Where V = vertices, E = edges, F = faces (regions, including the outer infinite face).

Example: A cube graph has V=8, E=12, F=6. Check: 8 - 12 + 6 = 2. ✓

Kuratowski's theorem: A graph is planar if and only if it doesn't contain K₅ (complete graph on 5 nodes) or K₃,₃ (complete bipartite graph) as a subdivision.

Applications: Circuit board design (minimize crossings), map layouts, network topology design.

Graph Isomorphism

Two graphs are isomorphic if there's a relabeling of nodes making them identical.

Graph isomorphism problem: Determine if two graphs are isomorphic.

For decades, this was neither known to be in P nor proven NP-complete. In 2015, László Babai claimed a quasi-polynomial algorithm, though debates continue.

Why it matters: Matching molecular structures (drug discovery), detecting duplicate networks, pattern recognition.

Random Graphs

Erdős–Rényi model: Start with n nodes, add each possible edge with probability p.

Phase transition: At p = 1/n, a giant connected component suddenly emerges. Below this threshold, the graph is fragmented. Above, it's connected.

This models network formation—social networks, neural networks, the early internet. Small changes in connection probability cause abrupt structural shifts.

Applications Everywhere

Graph theory isn't abstract. It's the skeleton of the digital world.

Google: PageRank is graph centrality. Search results rank pages by their position in the web graph.

Facebook: Social graph. Friend recommendations are graph algorithms (friends-of-friends, community detection).

GPS/Maps: Shortest path algorithms (Dijkstra, A*). Real-time routing adjusts for traffic (dynamic edge weights).

Internet routing: Packets route via shortest paths through the network graph.

Recommendation engines: Netflix, Amazon, Spotify model user-item interactions as bipartite graphs. Collaborative filtering = graph traversal.

Epidemiology: Disease spread modeled on contact networks. Network structure determines outbreak dynamics.

Biology: Protein interaction networks, gene regulatory networks, neural connectivity.

Logistics: Delivery routes, supply chains, warehouse optimization—all graph problems.

Every time you use an app, watch a video, get directions, or see a recommendation, graph algorithms are running underneath.

Why Graph Theory Matters

Euler solved a bridge puzzle and accidentally invented the mathematics of relationships.

Graphs abstract away irrelevant details—distances, shapes, physical properties—and keep only structure: what connects to what. This abstraction is powerful because structure determines behavior.

• Does information flow? Graph connectivity.
• Who's influential? Centrality measures.
• What's the fastest route? Shortest path algorithms.
• How resilient is this network? Robustness analysis.
• Where are the communities? Clustering algorithms.

Graph theory reveals that networks—social, biological, digital—aren't random. They have structure, patterns, and laws. Understanding graphs means understanding how the world connects.

Further Reading

• West, Douglas B. Introduction to Graph Theory. Prentice Hall, 2nd edition, 2001.
• Newman, Mark. Networks: An Introduction. Oxford University Press, 2010.
• Bondy, J.A., and U.S.R. Murty. Graph Theory. Springer, 2008.
• Euler, Leonhard. "Solutio problematis ad geometriam situs pertinentis." Commentarii Academiae Scientiarum Petropolitanae, 1741. (The original Königsberg paper)
• Barabási, Albert-László. Network Science. Cambridge University Press, 2016. (Free online textbook)

This is Part 6 of the Discrete Mathematics series, exploring the foundational math of computer science, algorithms, and computational thinking. Next: "Trees in Graph Theory — Connected, Hierarchical, Everywhere."

Part 6 of the Discrete Mathematics series.

Previous: The Binomial Theorem: Expanding Powers Next: Trees: Connected Graphs Without Cycles