Introduction to Graph Theory

Graph theory is a branch of mathematics that studies structures used to model pairwise relationships between objects. It has deep applications in computer science, network analysis, artificial intelligence, route optimisation, and even chemistry.

Graph

A graph $G$ is an ordered pair $(V, E)$ , where $V$ is a non-empty set of vertices (also called nodes) and $E$ is a set of edges — connections between pairs of vertices.

Graphs give us a flexible language for representing almost any system of connections:

People in a social network connected by friendships
Cities on a map connected by roads
Web pages connected by hyperlinks
Atoms in a molecule connected by chemical bonds

Analogy

Think of a graph like an airline route map. Each airport is a vertex, and each direct flight route between two airports is an edge. The whole network of flights forms a graph — and graph theory gives us tools to answer questions like "What is the shortest connecting route from A to B?"

Formally, if we have three people A, B, and C where A is friends with B and B is friends with C, we write:
$V = {A, B, C}, E = {{A, B}, {B, C}}$

Note that edges in an undirected graph are written as unordered pairs ${u, v}$ , since the connection has no direction.

Vertices, Edges, and Degree

Adjacent Vertices

Two vertices are adjacent if they are connected by an edge. Two edges are adjacent if they share a common vertex.

Degree of a Vertex

The degree of a vertex $v$ , written $de g (v)$ , is the number of edges incident to (connected to) that vertex.

For an undirected graph, the degree is simply how many edges meet at that vertex.

Example

Example: Calculating degrees

Given the graph with $V = {A, B, C, D}$ and $E = {{A, B}, {A, C}, {B, C}, {B, D}}$ :

$de g (A) = 2$ (connected to B and C)
$de g (B) = 3$ (connected to A, C, and D)
$de g (C) = 2$ (connected to A and B)
$de g (D) = 1$ (connected only to B)

Notice that the sum of all degrees $= 2 + 3 + 2 + 1 = 8$ , which equals twice the number of edges (4 edges × 2 = 8). This is always true — it is known as the Handshaking Lemma.

Note

Handshaking Lemma: For any graph $G$ with edge set $E$ ,
$\sum_{v \in V} de g (v) = 2∣ E ∣$
This means the sum of all vertex degrees is always even. As a consequence, the number of vertices with odd degree must be even.

In a directed graph (digraph), edges have direction, so we distinguish:

In-degree: number of edges entering the vertex
Out-degree: number of edges leaving the vertex

Free preview

AHL 3.14—Graph theory

Introduction to Graph Theory

Vertices, Edges, and Degree

11 more sections in this topic