Graph theory

Undirected graphs

Vertices and edges

A graph is a set of vertices \(V\), a set of edges E which are subset of pairs from V.

undirected so each edge is a set

Degree of a vertex

The degree of a vertex is the number of edges connections to it.

Order and size of graphs

The order of a graph is the number of vertices, \(|V|\).

The size of a graph is the number of edges, \(|E|\).


We can take a subset of vertices, and all edges which only depend on these vertices. This is an induced subgraph.

Induced subgraph

Loops, multiple edges and simple graphs


A loop is an edge where both the vertices are the same.

Multiple edges

If there are two edges with the same pair of indices, there are multiple edges.

Simple graphs

No loops or multiple edges.

Directed graphs

Direct acyclic graphs

Weighted graphs

Edge-weighted graph

An edge-weighted graphs has weights for each edge.

Vertex-weighted graph

A vertex-weighted graph has weights for each vertex.

Graph representation

Adjacency matrix

We can represent a finite graph as a square matrix. \(m_{ij}\) is the number of edges connecting vertex \(i\) to vertex \(j\).

Incidence matrix

An incidence matrix has \(m_{ij}\) representing the number of connections from vertex \(i\) to edge \(j\).

Degree matrix

A degree matrix is a diagonal matrix. Each diagonal contains the degree of the a vertex.

Laplacian matrix

The Laplacian matrix \(L\) is formed using the degree matrix \(D\) and the adjacency matrix \(A\). \(L=D-A\).

Representing manifolds

Nearest-neighbour graph

Triangular mesh

Edge colouring