Graph Theory Theorems

# 1. Theorems

# 1.1 Euler's Theorem

Theorem: A connected graph $G = (V, E)$ is considered Eulerian if and only if all vertices in $V(G)$ have an even degree, otherwise the graph is not Eulerian. |

## 1.11 Corollary 1

Corollary: If a graph G has 2m odd vertices, then the graph can be drawn in precisely m strokes. |

# 1.2 Dirac's Theorem

Theorem: If $G = (V, E)$ is a connected graph on n-vertices so that for every $x, y \in V(G)$ where $x ≠ y$, the $\deg (x) + \deg (y) ≥ n$ for all x and y, then G is Hamiltonian. |

# 1.3 Ore's Theorem

Theorem: If $G = (V, E)$ is a connected graph on n-vertices so that for every $x, y \in V(G)$ where $x ≠ y$, the $\deg (x) + \deg (y) ≥ n$ for all pairs of x and y that are adjacent, then G is Hamiltonian. |

# 1.4 Cayley's Theorem

Theorem: For $n ≥ 1$, there are precisely $n^{n - 2}$ tree graphs on n-labelled vertices. |

# 1.5 Kuratowski's Theorem

Theorem: A graph G is planar if it does not contain any subdivisions of $K_5$ or $K_{3,3}$. |

# 1.6 Brook's Theorem

Theorem: If G is a connected simple graph, and is not a complete graph or a cycle graph with an odd number of vertices, then the chromatic number $\chi (G) ≤ \Delta (G)$. |

# 1.7 Vizing's Theorem

Theorem: For any graph, $\Delta (G) ≤ \chi ' (G) ≤ \Delta (G) + 1$. |

# 2. Algorithms

## 2.1 Kruskal's Algorithm

Step 1 | Label each vertex (e.g. x_{1}, x_{2}, … or a, b, c, etc… ). |
---|---|

Step 2 | List the edges in non-decreasing order of weight. |

Step 3 | Start with the smallest weighted and beginning growing the minimum weighted spanning tree from this edge. |

Step 4 | Add the next available edge that does not form a cycle to the construction of the minumum weighted spanning tree. If the addition of the next least weighted edge forms a cycle, do not use it. |

Step 5 | Continue with step 4 until you have a spanning tree. |

## 2.2 Prim's Algorithm

Step 1 | First begin with any vertex in the graph. |
---|---|

Step 2 | Of all of the edges incident to this vertex, select the edge with the smallest weight. |

Step 3 | Repeat step 2 using the edges incident with the new vertex and that aren't already drawn. Repeat until a spanning tree is created. |