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

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

## 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

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$$.