FoldUnfold Table of Contents Ramsey Numbers Ramsey Numbers Definition: The Ramsey Number, $R(s,t)$ is the least positive integer $n$ such that for any edge $2$-colouring of $E(K_n)$, there exists either a $K_s$ or a $K_t$ with a monochromatic colouring. For example, the Ramsey number $R(3, 3) = 6$. We can prove this by seeing if $R(3, 3) \leq 6$. First, suppose that $R(3, … [Read more...]

## Graph Matchings

FoldUnfold Table of Contents Graph Matchings Graph Matchings Definition: For a graph $G = (V(G), E(G))$, a Matching is a subset $M \subset E(G)$ where no two edges in $M$ share a vertex. For example, suppose that we have a graph $G$ where $E(G) = \{ \{a, b\}, \{a, c\}, \{a, d \}, \{b, c \}, \{c, d \}, \{c, e \}, \{e , f \}$ we know that if $M = \{ \{ a, b \}, \{c, d \}, … [Read more...]

## Vizing’s Theorem

FoldUnfold Table of Contents Vizing's Theorem Vizing's Theorem Theorem 1 (Vizing's Theorem): For any (simple) graph $G$ where $\chi ' (G)$ is the smallest integer $k$ for a good edge $k$-colouring and $\Delta (G)$ is the maximum degree in $G$, then $\Delta (G) \leq \chi ' (G) \leq \Delta (G) + 1$. We will not prove this theorem, however this tells us that for any simple … [Read more...]

## Edge Colouring and Chromatic Indexes

FoldUnfold Table of Contents Edge Colouring and Chromatic Indexes Edge Colouring and Chromatic Indexes We have already looked at Vertex Colouring and Chromatic Numbers, and now we are going to examine edge colouring and the analogous chromatic index. Suppose that we wanted to colour the edges of a graph such that no vertex contains two edges of the same colour. Of course, … [Read more...]

## Bounds for X(G)

FoldUnfold Table of Contents Bounds for X(G) Upper / Lower Bounds for X(G) Bounds for X(G) We are now going to look at some possible bounds for determining the chromatic number of a graph. For very large graphs, determining the chromatic number is often very difficult. These upper and lower bounds are often very important in determining $\chi$ for a graph $G$, since we can … [Read more...]

## 5 Colour Theorem for Planar Graphs

FoldUnfold Table of Contents 5 Colour Theorem for Planar Graphs 5 Colour Theorem for Planar Graphs We have already shown the proof for the 6 Colour Theorem for Planar Graphs, and now we will prove an even stronger result, the 5 colour theorem. Theorem 1: For a connected planar simple graph $G$, the vertices in $G$ can be coloured with $5$ or fewer colours for a good $5$ (or … [Read more...]

## 6 Colour Theorem for Planar Graphs

FoldUnfold Table of Contents 6 Colour Theorem for Planar Graphs 6 Colour Theorem for Planar Graphs Theorem 1: For a connected planar simple graph $G$, the vertices in $G$ can be coloured with $6$ or fewer colours for a good $6$ (or less) colouring of $G$, that is, a function $f$ exists, $f: V(G) \to \{1, 2, 3, ..., k \}$ where $1 \leq k \leq 6$ such that for every $x, y \in … [Read more...]

## Brooks’ Theorem

FoldUnfold Table of Contents Brooks' Theorem Brooks' Theorem Before we go on to see Brooks' theorem, we're first going to prove a very similar theorem that has less strength regarding the chromatic number of a graph. Theorem 1: If $G$ is a (simple) graph then $\chi (G) \leq \Delta (G) + 1$. Proof: Suppose that $G_1$ is a simple graph with one vertex. Because $G_1$ is … [Read more...]

## Vertex Colouring and Chromatic Numbers

FoldUnfold Table of Contents Vertex Colouring and Chromatic Numbers Vertex Colouring and Chromatic Numbers Imagine that we could take the vertices of a graph and colour or label them such that the vertices of any edge are coloured (or labelled) differently. This is what we recognize as vertex colouring Definition: A Good Vertex $k$-Colouring for $k \in \mathbb{Z^+}$ is a … [Read more...]

## Graph Duality

FoldUnfold Table of Contents Graph Duality Correspondences of Duals Duals of a Dual Graph Duality Definition: For a planar graph $G$, the dual of $G$ denoted $G^*$ is a graph obtained by replacing all faces in $G$ with vertices, and connecting vertices with edges if those faces share an edge. For example, let's look at the following graph $G$ and a dual of $G$, $G^*$: Note … [Read more...]