Graph Theory 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. x1, x2, … or a, b, c, etc… ). List the edges in non-decreasing order of weight. Start with the smallest weighted and beginning growing the minimum weighted spanning tree from this edge. 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. 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. Of all of the edges incident to this vertex, select the edge with the smallest weight. Repeat step 2 using the edges incident with the new vertex and that aren't already drawn. Repeat until a spanning tree is created.