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

11 more sections in this topic

Introduction to Graph Theory

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

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

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

AHL 3.14—Graph theory

Introduction to Graph Theory

Vertices, Edges, and Degree

11 more sections in this topic