Graph Theory and Network Models

Introduction

Graph theory provides a mathematical language for systems whose behavior depends on relationships. Communication links between routers, roads between cities, friendships between users, dependencies among software modules, and assignments of workers to tasks can all be represented as graphs. Once modeled, these systems can be analyzed using algorithms for traversal, connectivity, shortest paths, spanning trees, matching, coloring, flow, and planarity.

A graph model deliberately abstracts away some real-world detail. Its value depends on selecting appropriate vertices, edges, directions, weights, capacities, and constraints. Consequently, graph modeling combines mathematical reasoning with domain knowledge and responsible interpretation.

Learning Objectives

After studying this chapter, students should be able to:

• define directed, undirected, weighted, simple, and multigraph models;
• represent graphs using adjacency lists, matrices, and edge lists;
• analyze degrees, paths, cycles, components, and connectivity;
• distinguish Eulerian, Hamiltonian, and tree-related properties;
• apply breadth-first and depth-first traversal;
• compute shortest paths and minimum spanning trees;
• formulate matching, coloring, and network-flow problems;
• use Euler's formula and edge bounds to reason about planar graphs;
• model communication, social, transport, and dependency networks; and
• evaluate limitations, governance concerns, and ethical risks in network analysis.

1. Graph Foundations

A graph is an ordered pair G=(V,E), where V is a nonempty set of vertices and E is a set of edges connecting vertices. The order of a graph is |V|, and its size is |E|.

In an undirected graph, an edge \{u,v\} has no orientation. In a directed graph, or digraph, an edge (u,v) points from u to v. A weighted graph associates a numerical value with each edge through a function w:E\to\mathbb{R}. Depending on the application, a weight may represent distance, cost, time, reliability, or another quantity. A capacity is an upper limit rather than an ordinary additive cost.

Two vertices are adjacent when an edge joins them. An edge is incident on each of its endpoints. A loop joins a vertex to itself. Unless stated otherwise, basic degree and planarity results in this chapter concern finite graphs.

1.1 Degree and the Handshaking Lemma

The degree \deg(v) of a vertex in an undirected graph is the number of incident edge ends; a loop contributes two. For a finite undirected graph with m=|E| edges,

Each edge contributes once at each endpoint, which proves the handshaking lemma. It follows that the number of odd-degree vertices is even.

For a directed graph, \deg^-(v) is the indegree and \deg^+(v) is the outdegree. If the digraph has m directed edges, then

1.2 Graph Representations

For vertices v₁,\ldots,v_n, the adjacency matrix A of a simple unweighted graph has entries

An undirected graph has a symmetric adjacency matrix. For a simple graph, diagonal entries are zero. In a weighted adjacency matrix, entries may store weights, but a separate symbol such as \infty is needed to distinguish a missing edge from an edge of weight zero.

An adjacency list stores each vertex's neighbors. With n=|V| and m=|E|, it requires O(n+m) space and is usually preferred for sparse graphs. An adjacency matrix requires O(n²) space but tests adjacency in constant time. An edge list is compact and useful for algorithms such as Kruskal's algorithm.

2. Walks, Paths, Cycles, and Connectivity

A walk is a sequence of vertices in which consecutive vertices are joined by edges. A trail does not repeat edges, while a path does not repeat vertices. A closed path of length at least three is a cycle in a simple graph.

An undirected graph is connected if every pair of vertices has a path between them. A maximal connected subgraph is a connected component. A vertex whose deletion increases the number of components is an articulation vertex. An edge whose deletion increases that number is a bridge. Such elements often identify single points of failure.

In a digraph, vertices u and v are strongly connected if each is reachable from the other. A strongly connected component is a maximal set of mutually reachable vertices. Contracting every strongly connected component produces a directed acyclic graph (DAG), called the condensation graph.

2.1 Eulerian and Hamiltonian Problems

An Euler trail uses every edge exactly once. A connected undirected graph has an Euler circuit if and only if every vertex has even degree. It has an open Euler trail if and only if exactly two vertices have odd degree. Isolated vertices may be disregarded when stating connectivity for this criterion.

A Hamiltonian path visits every vertex exactly once, and a Hamiltonian cycle returns to its starting point. Unlike the Euler criterion, no simple necessary-and-sufficient degree test is known for general Hamiltonian graphs. Determining whether an arbitrary graph has a Hamiltonian cycle is NP-complete.

The distinction is practical: street inspection focuses on covering edges and is often Eulerian, whereas a tour visiting each destination once is Hamiltonian.

3. Trees and Hierarchical Models

A tree is a connected undirected graph containing no cycle. For a finite graph with n vertices, any two of the following properties imply the others:

• the graph is connected and acyclic;
• it is connected and has n-1 edges;
• it is acyclic and has n-1 edges;
• there is exactly one simple path between every pair of vertices;
• removing any edge disconnects it.

A forest is an acyclic graph whose components are trees. If a forest has n vertices and k components, it has n-k edges.

A rooted tree distinguishes one vertex as the root. Every non-root vertex then has one parent, while vertices immediately below it are children. Rooted trees model file systems, syntax, organizational hierarchies, search spaces, and recursive computation.

For a full binary tree, every internal vertex has exactly two children. If i is the number of internal vertices and l the number of leaves, then

This identity is special to full binary trees; it does not hold for arbitrary rooted trees.

4. Graph Traversal

Traversal systematically explores reachable vertices. With adjacency lists, breadth-first search (BFS) and depth-first search (DFS) both run in O(n+m) time.

4.1 Breadth-First Search

BFS explores vertices in nondecreasing distance from a source. It uses a queue:

1. Mark the source discovered and enqueue it.
2. Dequeue a vertex u.
3. Discover and enqueue each undiscovered neighbor of u.
4. Continue until the queue is empty.

In an unweighted graph, BFS computes a shortest path measured by number of edges. The predecessor links form a BFS tree. BFS also tests connectivity and determines whether a graph is bipartite by assigning alternating levels or colors.

4.2 Depth-First Search

DFS follows one branch as deeply as possible before backtracking. It can be implemented recursively or with an explicit stack. DFS supports cycle detection, articulation-point detection, strongly connected component algorithms, and topological sorting.

A topological ordering of a digraph places every vertex before all vertices reached by its outgoing edges. Such an ordering exists if and only if the digraph is acyclic. It is useful for course prerequisites, build systems, package installation, and task scheduling.

Figure: BFS discovers vertices by increasing unweighted distance from source A.

5. Shortest-Path Models

A path's weight is the sum of its edge weights. Shortest-path algorithms depend on the assumptions imposed on those weights.

Dijkstra's algorithm maintains tentative distances. For an edge (u,v) of weight w(u,v), relaxation tests

If true, it sets d(v)=d(u)+w(u,v) and records u as the predecessor of v. Dijkstra finalizes a currently minimum tentative distance; its correctness depends on nonnegative edge weights.

Worked Example: Dijkstra's Algorithm

Suppose the directed edges are A\to B=4, A\to C=1, C\to B=2, B\to D=1, and C\to D=5, where weights are travel times in minutes.

Initially, d(A)=0 and all other distances are infinite. Relaxing edges from A gives d(B)=4 and d(C)=1. Vertex C is selected next; relaxing through it changes d(B) to 1+2=3 and gives d(D)=6. Processing B changes d(D) to 3+1=4. Therefore, the shortest path is A\to C\to B\to D, with total time 4 minutes.

If weights represent changing travel times, a static shortest path may become obsolete. Time-dependent routing requires models that specify when an edge is entered and whether waiting is allowed.

6. Minimum Spanning Trees

For a connected, weighted, undirected graph, a spanning tree contains every vertex. A minimum spanning tree (MST) minimizes the total edge weight among all spanning trees.

Kruskal's algorithm sorts edges by nondecreasing weight and adds an edge whenever it connects two currently separate components. A disjoint-set data structure efficiently detects cycles. Prim's algorithm grows one tree, repeatedly choosing the lightest edge crossing from the current tree to an outside vertex.

The cut property states that, for any cut of a weighted undirected graph, a minimum-weight edge crossing that cut belongs to some MST. If it is the unique minimum crossing edge, it belongs to every MST.

Worked Example: Kruskal's Algorithm

Let the edges be AB=1, BC=2, CD=3, AC=6, and AD=8, with costs in thousands of currency units. Kruskal's algorithm selects AB, BC, and CD. These three edges connect all four vertices without a cycle, so the MST cost is

An MST minimizes construction cost but need not provide redundancy, low delay between every pair, or resilience against failures. Engineering design often supplements an MST with backup links.

7. Matching and Assignment

A matching is a set of edges with no shared endpoint. A maximum matching contains as many edges as possible. A perfect matching covers every vertex.

Matching is especially important in bipartite graphs G=(X\cup Y,E), where every edge joins a vertex in X to one in Y. Examples include students and projects, servers and jobs, or donors and recipients.

For S\subseteq X, let N(S) denote all neighbors of vertices in S. Hall's marriage theorem states that a finite bipartite graph contains a matching that covers every vertex of X if and only if

The condition means that every group of applicants collectively has at least as many eligible positions as applicants. Weighted assignment problems seek minimum cost or maximum benefit rather than merely maximum cardinality.

8. Graph Coloring

A proper vertex coloring assigns colors to vertices so that adjacent vertices receive different colors. The minimum number of colors required is the chromatic number \chi(G). Colors can represent examination periods, frequencies, registers, or mutually exclusive resources.

Every bipartite graph with at least one edge has chromatic number two. Equivalently, an undirected graph is bipartite if and only if it has no odd-length cycle. A greedy coloring algorithm processes vertices sequentially and assigns the smallest available color. It uses at most \Delta(G)+1 colors, where \Delta(G) is maximum degree, but it need not be optimal.

Coloring decisions can be order-sensitive. Determining whether a general graph is colorable with at most three colors is NP-complete, so heuristics and approximation methods are often used for large instances.

9. Network Flows

A flow network is a directed graph with source s, sink t, and nonnegative edge capacities c(u,v). A feasible flow f(u,v) satisfies capacity constraints

and flow conservation at every intermediate vertex:

The flow value |f| is the total flow leaving the source minus any flow entering it; equivalently, it is the net flow entering the sink.

An s–t cut partitions the vertices into sets S and T with s\in S and t\in T. Its capacity is the sum of capacities of edges directed from S to T. The max-flow min-cut theorem states that the maximum feasible flow value equals the minimum cut capacity.

Ford–Fulkerson repeatedly augments flow along source-to-sink paths in the residual graph. If capacities are integers, it can produce an integral maximum flow. Edmonds–Karp chooses augmenting paths using BFS and runs in O(nm²).

Worked Example: Correct Capacity Analysis

Consider edges with capacities, in Gbit/s:

• s\to a=5;
• s\to b=8;
• a\to t=4;
• b\to t=8.

The total capacity entering t is 4+8=12 Gbit/s, so no feasible flow can exceed 12 Gbit/s. A feasible flow achieving this bound sends 4 Gbit/s along s\to a\to t and 8 Gbit/s along s\to b\to t. Therefore,

Sending 5 Gbit/s through a\to t would violate its 4 Gbit/s capacity. The cut immediately before the sink has capacity 12 Gbit/s and proves optimality.

Figure: The sink-side cut limits total throughput to 12 Gbit/s.

10. Planar Graphs

A graph is planar if it can be drawn in the plane without edge crossings except at common endpoints. A particular crossing-free drawing is a plane graph. Faces are the regions formed by a plane embedding, including the unbounded outer face.

For a connected plane graph with n vertices, m edges, and r faces, Euler's formula is

For a simple connected planar graph with n\ge3, every face boundary has length at least three. Counting edge incidences around faces gives 3r\le2m. Combining this with Euler's formula yields

This is a necessary, not sufficient, condition for planarity. If the graph is also bipartite, it has no triangles, so each face boundary has length at least four. For a simple connected planar bipartite graph with n\ge3,

The complete graph K₅ violates the first bound, while K_3,3 violates the bipartite bound. Kuratowski's theorem characterizes planar graphs as those containing no subdivision of K₅ or K_3,3. Planarity matters in circuit layout, geographic networks, and visualization, although physical networks may use bridges, tunnels, or layered circuit boards and therefore need not be planar.

11. Applied Case: Regional Data Network Upgrade

This is an illustrative case.

Background

A regional cloud provider connects a source data center s to an aggregation destination t through routers a and b. Link capacities are measured in Gbit/s. The routes and capacities are s\to a=5, s\to b=8, a\to t=4, and b\to t=8.

Problem

Engineers must determine current maximum throughput and choose an effective one-link upgrade. A preliminary proposal recommends increasing only the capacity of s\to a.

Analysis

The source can transmit at most 5+8=13 Gbit/s, but the two links entering the destination carry at most 4+8=12 Gbit/s. Thus, the sink-side cut is the tighter bound. A feasible 12 Gbit/s flow exists: 4 Gbit/s through router a and 8 Gbit/s through router b. By the max-flow min-cut theorem, 12 Gbit/s is optimal.

Increasing only s\to a cannot raise throughput while a\to t remains limited to 4 Gbit/s. In contrast, increasing a\to t from 4 to 5 Gbit/s changes the total destination-side capacity to 13 Gbit/s. The network can then send 5 Gbit/s through a and 8 Gbit/s through b, giving a feasible maximum flow of 13 Gbit/s.

Approach and Solution

The provider should upgrade a\to t to 5 Gbit/s if its immediate objective is to gain 1 Gbit/s of aggregate throughput with one link change. After that upgrade, both the source-side and sink-side cuts have capacity 13 Gbit/s.

A capacity-only solution does not guarantee resilience. Failure of the 8 Gbit/s branch would reduce service severely. A broader design should consider redundant routes, latency, equipment reliability, security controls, upgrade cost, and expected traffic growth.

Outcome

The corrected design increases maximum throughput from 12 to 13 Gbit/s without violating any link capacity. It also demonstrates why local link utilization is insufficient: the decisive object is the minimum cut across the entire network.

Learning Points

• An upper bound from a cut must be paired with a feasible flow to establish optimality.
• Increasing capacity outside the current bottleneck cut may produce no improvement.
• Increasing a\to t can raise this network's throughput to 13 Gbit/s.
• Throughput, resilience, delay, and security are distinct design objectives.

12. Modeling Major Network Types

Communication Networks

Vertices represent devices, and edges represent wired or wireless links. Capacities model bandwidth; weights may model delay, energy, or monetary cost. Routing may require multiobjective optimization because the minimum-delay path need not have the highest capacity or reliability.

Social Networks

Vertices represent actors and edges represent relationships or interactions. Degree, centrality, communities, and diffusion models can reveal structural patterns. However, an observed digital interaction does not necessarily imply friendship, influence, or agreement. Sampling and platform design can distort conclusions.

Transport Networks

Vertices may be intersections, stations, or cities; edges represent roads or services. Direction, time-dependent travel, transfer penalties, and congestion are important. Ordinary shortest-path models assume edge costs can be meaningfully added and are known for the relevant travel period.

Dependency Networks

Directed edges represent prerequisites or dependence. A DAG supports topological ordering and scheduling. A directed cycle may reveal mutually dependent packages or an impossible prerequisite specification. Strongly connected component analysis localizes such cycles.

13. Challenges, Governance, and Contemporary Practice

A graph is only as reliable as its data and assumptions. Missing edges can distort connectivity, while stale weights can invalidate routes. Aggregation may conceal differences between users, locations, or time periods. Large dynamic graphs also create computational and storage challenges.

Network data can be highly sensitive. Social connections, communication metadata, and mobility traces may reveal identity, health status, political activity, or organizational structure. Responsible practice includes purpose limitation, access control, retention policies, anonymization where appropriate, and compliance with relevant privacy and cybersecurity regulation. Simple removal of names may not prevent re-identification because graph structure itself can be distinctive.

Algorithmic decisions also require fairness analysis. A matching system may maximize total score while repeatedly disadvantaging a group. Routing can shift congestion or pollution toward particular communities. Centrality measures may be misinterpreted as measures of social worth or culpability.

Contemporary systems increasingly combine graph algorithms with graph databases, distributed processing, graph neural networks, and streaming analytics. Machine learning can estimate missing links or traffic weights, but predicted edges should not automatically be treated as facts. Explainability, uncertainty reporting, validation, and human oversight remain essential.

Recommended professional practices include:

• document what vertices, edges, directions, and weights mean;
• state units and distinguish cost, capacity, probability, and similarity;
• validate algorithm assumptions before deployment;
• test sensitivity to missing data and changing weights;
• use cut, path, and component analyses to identify failure risks;
• separate optimization objectives from ethical and legal constraints; and
• monitor deployed network models as the real system evolves.

Chapter Summary

Graphs model entities and relationships using vertices and edges. Degree identities, paths, cycles, components, and strong connectivity provide fundamental structural information. Trees model hierarchy and minimal connectivity, while BFS and DFS support systematic exploration. BFS solves unweighted shortest-path problems; Dijkstra's algorithm requires nonnegative weights, whereas Bellman–Ford accommodates negative edges when no relevant negative cycle exists.

Minimum spanning trees minimize total connection cost but do not inherently provide resilience. Bipartite matching supports assignment, and Hall's theorem characterizes when one side can be completely matched. Coloring represents conflicts and resource separation. Maximum-flow models combine capacity constraints with conservation, and the max-flow min-cut theorem identifies throughput bottlenecks. Euler's formula and planar edge bounds support reasoning about crossing-free layouts. Effective graph modeling also requires attention to units, dynamic behavior, incomplete data, privacy, security, fairness, and the distinction between mathematical optimality and operational suitability.

Key Terms

Adjacency: The relationship between vertices joined by an edge.

Articulation vertex: A vertex whose removal increases the number of connected components.

Bipartite graph: A graph whose vertices can be divided into two sets with every edge crossing between the sets.

Bridge: An edge whose removal increases the number of connected components.

Capacity: The maximum permitted flow through an edge.

Chromatic number: The minimum number of colors needed for a proper vertex coloring.

Connected component: A maximal connected subgraph.

Cut: A partition of a network's vertices that separates the source from the sink.

Directed acyclic graph: A directed graph containing no directed cycle.

Flow: A capacity-constrained quantity transmitted through a network while satisfying conservation.

Graph: A set of vertices together with edges representing relationships.

Matching: A set of edges with no shared endpoints.

Minimum spanning tree: A spanning tree of minimum total edge weight.

Path: A walk that does not repeat vertices.

Planar graph: A graph admitting a drawing without edge crossings except at endpoints.

Strongly connected component: A maximal vertex set in which every vertex can reach every other vertex by directed paths.

Tree: A connected, acyclic, undirected graph.

Weight: A numerical edge attribute such as cost, time, or distance.

Review Questions

Short Answer Questions

1. Distinguish a walk, trail, path, and cycle.
2. State the handshaking lemma and one consequence of it.
3. Why does BFS compute shortest paths in an unweighted graph?
4. What condition must hold for a topological ordering to exist?
5. Distinguish an MST objective from a maximum-flow objective.

Long Answer Questions

1. Compare adjacency matrices, adjacency lists, and edge lists in terms of space, operations, and applications.
2. Explain BFS and DFS, including their data structures, complexity, and major uses.
3. Compare Dijkstra, Bellman–Ford, and Floyd–Warshall algorithms, emphasizing their assumptions.
4. Explain the max-flow min-cut theorem and how residual networks support augmenting-path algorithms.
5. Derive the planar edge bound m\le3n-6 and explain its limitations.

Analytical / Application Questions

1. Model a university prerequisite system as a directed graph. Explain how cycles and topological sorting would be used to validate the curriculum.
2. A transport planner proposes using an MST as the complete road design for emergency services. Analyze the benefits and risks of this choice.
3. For the case-study network, evaluate the throughput effects of separately increasing s\to a to 6 Gbit/s and a\to t to 5 Gbit/s. Justify each answer using cuts and feasible flows.

Multiple Choice Questions with Answers

Question 1

An undirected graph has 9 edges. What is the sum of all vertex degrees?

A. 9

B. 16

C. 18

D. 81

Correct Answer: C. 18

Question 2

How many edges does a tree with 20 vertices have?

A. 18

B. 19

C. 20

D. 21

Correct Answer: B. 19

Question 3

Which algorithm directly computes shortest paths by number of edges from one source in an unweighted graph?

A. Breadth-first search

B. Depth-first search

C. Kruskal's algorithm

D. Floyd's cycle-detection algorithm

Correct Answer: A. Breadth-first search

Question 4

Which condition is required for the standard correctness guarantee of Dijkstra's shortest-path algorithm?

A. The graph must be complete

B. All edge weights must be nonnegative

C. Every vertex must have even degree

D. The graph must be planar

Correct Answer: B. All edge weights must be nonnegative

Question 5

A connected weighted graph has edges AB=1, BC=2, CD=3, AC=6, and AD=8. What is the MST weight?

A. 5

B. 6

C. 9

D. 11

Correct Answer: B. 6

Question 6

According to Hall's theorem, a bipartite graph G=(X\cup Y,E) has a matching covering every vertex of X precisely when which condition holds?

A. Every vertex of X has degree two

B. |X|=|Y|

C. |N(S)|\ge|S| for every S\subseteq X

D. The graph contains no even cycle

Correct Answer: C. |N(S)|\ge|S| for every S\subseteq X

Question 7

What is the chromatic number of a connected bipartite graph containing at least one edge?

A. 1

B. 2

C. 3

D. It always equals the maximum degree

Correct Answer: B. 2

Question 8

A simple connected planar graph has 8 vertices. What is the largest number of edges permitted by the general planar edge bound?

A. 14

B. 16

C. 18

D. 24

Correct Answer: C. 18

Question 9

A flow network has capacities s\to a=5, s\to b=8, a\to t=4, and b\to t=8, all in Gbit/s. What is its maximum flow?

A. 9 Gbit/s

B. 11 Gbit/s

C. 12 Gbit/s

D. 13 Gbit/s

Correct Answer: C. 12 Gbit/s

Question 10

Which statement about topological ordering is correct?

A. Every connected undirected graph has exactly one topological ordering

B. A directed graph has a topological ordering if and only if it is acyclic

C. A directed graph has a topological ordering if and only if all vertices have equal indegree

D. Only weighted graphs can be topologically ordered

Correct Answer: B. A directed graph has a topological ordering if and only if it is acyclic