Chapter 1. What Graph Theory Is

Graph theory is the study of objects and the relations between them.

The objects are called vertices. The relations are called edges. A graph records which objects are connected to which other objects. This simple idea gives a precise language for networks, maps, dependencies, routes, states, games, circuits, molecules, programs, and many other discrete structures.

A graph is usually written as

G = (V, E).

Here $V$ is the set of vertices, and $E$ is the set of edges. In a simple undirected graph, each edge connects two distinct vertices, and no pair of vertices is connected by more than one edge. This is the default kind of graph used in many introductory treatments.

1.1 Vertices and Edges

A vertex is a basic point of a graph. It may represent a city, a person, a web page, a task, a variable, a state, or an abstract mathematical object.

An edge is a connection between two vertices. If $u$ and $v$ are vertices, then an undirected edge between them is written as

\{u, v\}.

The order does not matter. The edge $\{u, v\}$ is the same edge as $\{v, u\}$ .

For example, let

V = \{a, b, c, d\}

and

E = \{\{a,b\}, \{a,c\}, \{b,d\}, \{c,d\}\}.

Then $G = (V,E)$ is a graph with four vertices and four edges.

The graph says that $a$ is connected to $b$ and $c$ , that $b$ is connected to $d$ , and that $c$ is connected to $d$ . It says nothing about positions, distances, angles, or shapes unless extra structure is added.

1.2 Graphs as Models

A graph keeps only adjacency information. It records whether two vertices are joined.

This makes graphs useful when the exact geometry is less important than the pattern of connection.

Situation	Vertices	Edges
Road network	Intersections or cities	Roads
Social network	People	Friendships or follows
Web graph	Web pages	Links
Task dependency graph	Tasks	Dependency relations
Circuit graph	Components or terminals	Wires
Molecular graph	Atoms	Chemical bonds
Compiler graph	Symbols or modules	References or imports

The same mathematical object can describe each situation. The interpretation changes, but the underlying structure remains a set of vertices and a set of edges.

1.3 Undirected Graphs

An undirected graph has edges without direction.

If an undirected edge connects $u$ and $v$ , then one may move from $u$ to $v$ and from $v$ to $u$ along the same edge. This is suitable for symmetric relations, such as “is connected by a road to” or “is married to” in a simplified model.

Formally, an undirected graph is written

G = (V,E),

where each edge in $E$ is a two-element subset of $V$ .

If $\{u,v\} \in E$ , then $u$ and $v$ are called adjacent. The edge $\{u,v\}$ is said to be incident with both $u$ and $v$ .

1.4 Directed Graphs

A directed graph, or digraph, has edges with direction. Directed edges are often called arcs.

A directed graph is written as

G = (V,A),

where $V$ is the set of vertices and $A$ is the set of directed edges. A directed edge from $u$ to $v$ is written as

(u,v).

Here order matters. The arc $(u,v)$ goes from $u$ to $v$ . It is generally different from $(v,u)$ .

Directed graphs model asymmetric relations.

Situation	Directed edge $u \to v$ means
Web graph	Page $u$ links to page $v$
Task system	Task $u$ must occur before task $v$
Social network	User $u$ follows user $v$
State machine	State $u$ can transition to state $v$
Citation graph	Paper $u$ cites paper $v$

Direction changes the meaning of reachability. In a directed graph, there may be a path from $u$ to $v$ without a path from $v$ to $u$ .

1.5 Degree

The degree of a vertex in an undirected graph is the number of edges incident with that vertex.

The degree of $v$ is written as

\deg(v).

For example, if

E = \{\{a,b\}, \{a,c\}, \{a,d\}, \{b,d\}\},

then

\deg(a) = 3, \qquad \deg(b) = 2, \qquad \deg(c) = 1, \qquad \deg(d) = 2.

Degree measures local connectivity. A vertex of high degree is connected to many neighbors. A vertex of degree zero is called isolated.

In a directed graph, one distinguishes between in-degree and out-degree. The in-degree of a vertex counts arcs entering it. The out-degree counts arcs leaving it.

1.6 Walks, Trails, Paths, and Cycles

Graphs are often studied through movement from vertex to vertex.

A walk is a sequence of vertices in which consecutive vertices are joined by edges. Vertices and edges may repeat.

A trail is a walk with no repeated edges.

A path is a walk with no repeated vertices.

A cycle is a closed path: it starts and ends at the same vertex, with no repeated vertices except the first and last. Standard references distinguish these terms because they support different theorems and algorithms.

Consider the graph with edges

\{a,b\}, \{b,c\}, \{c,d\}, \{d,a\}, \{a,c\}.

Then

a,b,c,d

is a path, while

a,b,c,d,a

is a cycle.

The length of a walk, trail, path, or cycle is the number of edges it uses.

1.7 Connectedness

An undirected graph is connected if every pair of vertices can be joined by a path.

If a graph is not connected, it splits into connected pieces called connected components. Each component is a largest connected subgraph.

For example, if

V = \{a,b,c,d,e\}

and

E = \{\{a,b\}, \{b,c\}, \{d,e\}\},

then the graph has two components:

\{a,b,c\}

and

\{d,e\}.

Connectedness is a global property. It asks whether the graph holds together as one piece.

In a directed graph, connectedness has several forms. A directed graph is strongly connected if every vertex can reach every other vertex by directed paths. It is weakly connected if it becomes connected after ignoring edge directions.

1.8 Complete Graphs

A complete graph is a graph in which every pair of distinct vertices is joined by an edge.

The complete graph on $n$ vertices is denoted by

K_n.

Thus $K_3$ is a triangle, $K_4$ has four vertices and six edges, and $K_n$ has every possible edge among $n$ vertices.

The number of edges in $K_n$ is

\frac{n(n-1)}{2}.

This formula counts the number of unordered pairs of distinct vertices.

Complete graphs are important because they represent maximum adjacency. They often appear as extremal examples, test cases, and building blocks.

1.9 Subgraphs

A subgraph is a graph contained inside another graph.

G = (V,E),

then a graph

H = (V_H,E_H)

is a subgraph of $G$ when

V_H \subseteq V

and

E_H \subseteq E.

The edges of $H$ must connect vertices that belong to $V_H$ .

Subgraphs allow one to study local structure inside a larger graph. Paths, cycles, trees, cliques, and components can all be viewed as subgraphs of a graph.

1.10 Isomorphism

Two graphs may look different when drawn but have the same structure.

Graph isomorphism formalizes this idea. Two graphs $G$ and $H$ are isomorphic if there is a bijection between their vertex sets that preserves adjacency.

If $f : V(G) \to V(H)$ is such a bijection, then

\{u,v\} \in E(G)

exactly when

\{f(u), f(v)\} \in E(H).

Isomorphic graphs have the same structure under relabeling. Their drawings may differ, but their adjacency pattern is identical.

This distinction is central in graph theory. A graph is an abstract object. A drawing is only one representation of that object.

1.11 Graph Representations

A graph can be represented in several ways.

An edge list stores all edges:

(a,b), (a,c), (b,d), (c,d).

An adjacency list stores the neighbors of each vertex:

Vertex	Neighbors
$a$	$b,c$
$b$	$a,d$
$c$	$a,d$
$d$	$b,c$

An adjacency matrix stores adjacency in a square matrix. If the vertices are ordered as $a,b,c,d$ , then the graph above has adjacency matrix

\begin{bmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{bmatrix}.

The entry in row $i$ , column $j$ is $1$ if the corresponding vertices are adjacent, and $0$ otherwise.

Each representation has different advantages.

Representation	Strength
Edge list	Simple and compact for sparse graphs
Adjacency list	Efficient for traversal
Adjacency matrix	Fast adjacency test
Incidence matrix	Useful for algebraic methods

The representation is not the graph itself. It is a way of storing or displaying the graph.

1.12 Graph Theory as Structure

Graph theory studies structure without relying on continuous measurement.

In geometry, distance and angle are primary. In graph theory, adjacency is primary. A graph does not need coordinates. It does not need a scale. It does not need a notion of straight line.

This discrete nature makes graph theory suitable for finite systems and combinatorial reasoning. Many graph problems ask whether a structure exists, how many such structures exist, or how efficiently one can find them.

Typical questions include:

Question	Example
Existence	Does the graph contain a cycle?
Optimization	What is the shortest path between two vertices?
Enumeration	How many spanning trees does the graph have?
Classification	Is the graph planar?
Coloring	How many colors are needed so adjacent vertices differ?
Connectivity	How many vertices must be removed to disconnect the graph?
Matching	Can every vertex be paired with a distinct neighbor?

These questions recur throughout the subject.

1.13 The Seven Bridges Problem

Graph theory is often traced to Euler’s solution of the Seven Bridges of Konigsberg problem in 1736. The problem asked whether one could walk through the city and cross each bridge exactly once.

Euler modeled land masses as vertices and bridges as edges. The question became a graph question about whether there is a closed trail using every edge exactly once. Such a trail is now called an Eulerian circuit. A connected undirected graph has an Eulerian circuit exactly when every vertex has even degree.

The importance of the problem lies in the modeling step. Euler ignored irrelevant geometric data and retained only the connection pattern. The resulting abstraction became the beginning of graph theory.

1.14 Pure and Applied Graph Theory

Graph theory has both pure and applied forms.

Pure graph theory studies graphs as mathematical objects. It investigates coloring, planarity, connectivity, matchings, minors, extremal problems, random graphs, spectra, and infinite graphs.

Applied graph theory uses graphs as models for systems. It appears in routing, scheduling, search engines, social networks, databases, chemistry, biology, compilers, distributed systems, machine learning, and optimization.

The boundary between pure and applied graph theory is often thin. A theorem about matchings may become an assignment algorithm. A theorem about eigenvalues may become a clustering method. A theorem about planarity may become a circuit layout tool.

1.15 Main Themes

This book develops graph theory through several recurring themes.

Theme	Description
Structure	What does the graph contain?
Connectivity	Which vertices can reach which others?
Traversal	How can we move through the graph?
Optimization	Which path, matching, cut, or coloring is best?
Representation	How should the graph be stored or computed?
Algebra	What do matrices reveal about the graph?
Probability	What happens in a random graph?
Algorithms	How efficiently can graph questions be answered?

These themes appear in elementary and advanced forms. A path in Chapter 1 later becomes shortest paths, flow paths, Hamiltonian paths, random walks, and paths in directed acyclic graphs. A simple edge later becomes a cut, a matching edge, a bridge, or an entry in a matrix.

1.16 Summary

Graph theory studies vertices and edges. A graph records relationships among objects by storing adjacency. The subject begins with simple definitions: vertex, edge, degree, path, cycle, connectedness, subgraph, and isomorphism.

Its power comes from abstraction. Once a system is represented as a graph, the same mathematical tools can be applied across many domains. A road map, a social network, a dependency graph, a circuit, and a web graph may have different meanings, but they can share the same graph structure.

The rest of the book develops this structure systematically.