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. x1, x2, … 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.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License