From e6ff6b0b8aada21f6a40c0c20ddcd3abcdc96f9b Mon Sep 17 00:00:00 2001
From: Adrian Kummerlaender
Date: Sun, 11 Feb 2018 22:19:40 +0100
Subject: Expand graph theory digest

---
 content/graph_theory.tex | 48 +++++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 43 insertions(+), 5 deletions(-)

diff --git a/content/graph_theory.tex b/content/graph_theory.tex
index 84e3222..10e4748 100644
--- a/content/graph_theory.tex
+++ b/content/graph_theory.tex
@@ -2,7 +2,7 @@
 
 A graph $G$ is the tuple $(V,E)$ where $V$ is a finite set of vertices and $E \subset {V \choose 2}$ is the set of edges.
 
-\subsection*{Notation}
+\subsection*{Notation of special graphs}
 
 $K_n$ is the complete graph on $n$ vertices.
 
@@ -14,20 +14,38 @@ $E_n$ is the empty i.e. edge-less graph on $n$ vertices.
 
 $K_{m,n}$ is the complete bipartite graph with partite sets of cardinality $m$ respectively $n$.
 
-\spacing
-
-$|G| := |V(G)|$ and $\|G\| := |E(G)|$
+\subsection*{Local properties}
 
 $N(v)$ for $v \in V(G)$ is the \emph{neighbourhood} of $v$.
 
 $d(v)$ for $v \in V(G)$ is the \emph{degree} of $v$.
 
+$d(u,v)$ is the length of a shortest $u$-$v$-path.
+
+\subsection*{Global properties}
+
+$|G| := |V(G)|$ and $\|G\| := |E(G)|$
+
 $\delta(G)$ is the minimum degree in $G$.
 
 $\Delta(G)$ is the maximum degree in $G$.
 
+\spacing
+
 $G$ is $k$-regular $\iff \forall v \in V(G) : d(v) = k$
 
+The \emph{girth} $g(G)$ is the length of a shortest cycle.
+
+The length of a longest cycle is $G$'s \emph{circumference}.
+
+\spacing
+
+$\text{diam}(G) := \displaystyle\max_{u,v \in V(G)} d(u,v)$ is the \emph{diameter} of $G$.
+
+\spacing
+
+$\text{rad}(G) := \displaystyle\min_{u \in V(G)} \max_{v \in V(G)} d(u,v)$ is the \emph{radius} of $G$.
+
 \subsection*{Induced Subgraphs}
 
 Subgraph $H \subset G$ is \emph{induced} if:
@@ -48,7 +66,11 @@ $G$ is \emph{bipartite} iff it has no cycles of odd length.
 
 \subsection*{Eulerian Tour Condition}
 
-A connected graph has an \emph{Eulerian Tour} iff every vertex has even degree.
+An \emph{Eulerian tour} is closed walk containing all edges of $G$ exactly once.
+
+\spacing
+
+A connected graph has an Eulerian tour iff every vertex has even degree.
 
 \subsection*{Hall's Marriage Theorem}
 
@@ -351,4 +373,20 @@ When $X$ counts e.g. the number of a certain class of subgraphs $\mathbb{E}(X)$
 \vspace*{-4mm}
 $$\mathbb{E}X = \mathbb{E}\left(\sum_{i=1}^N X_i\right) = \sum_{i=1}^N \mathbb{E}X_i = \sum_{i=1}^N \mathbb{P}(X_i=1)$$
 
+\subsection*{Erd\H{o}s-Hajnal}
+
+$\forall k \geq 3 \exists$ a graph $G$ s.t. $g(G), \chi(G) > k$.
+
 \section*{Hamiltonian Cycles}
+
+A \emph{Hamiltonian cycle} is a cycle that visits each vertex of $G$ exactly once.
+
+Correspondingly a \emph{Hamiltonian path} is a path that visits each vertex of $G$ exactly once.
+
+\subsection*{Dirac Theorem}
+
+Every graph $G$ with $|V(G)| \geq 3$ and $\delta(G) \geq \frac{n}{2}$ has a Hamiltonian cycle.
+
+\subsection*{Tutte Theorem}
+
+Every $4$-connected planar graph is Hamiltonian.
-- 
cgit v1.2.3