# 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|\).

### Subgraphs

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

#### Loops

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