\section*{Basics}

A \emph{graph} $G$ is a tuple $(V,E)$ where $V$ is a finite set of vertices and $E \subset {V \choose 2}$ is the set of edges.

\spacing

A \emph{multigraph} $G$ is a tuple $(V,E)$ where $V$ is a set of vertices and $E$ is a multiset of elements from ${V \choose 1} \cup {V \choose 2}$ i.e. multiedges and loops.

\spacing

A \emph{hypergraph} $H$ is a tuple $(X,E)$ where $X$ is a finite set and $E \subseteq 2^X \setminus \{\emptyset\}$.

i.e. edges may join any number of vertices.

\subsection*{Notation of special graphs}

$K_n$ is the complete graph on $n$ vertices.

$C_n$ is the cycle on $n$ vertices.

$P_n$ is a path of length $n$ where $n$ counts edges.

$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$.

\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*{Handshake Lemma}

\[ 2|E| = \sum_{v \in V} d(v) \]

Furthermore the sum of all degrees is even and thus \#vertices with odd degree is also even.

\subsection*{Induced Subgraphs}

Subgraph $H \subset G$ is \emph{induced} if:

$\forall u, v \in V(H) : uv \in E(H) \iff uv \in E(G)$

i.e. every induced subgraph may be generated by deleting vertices and their incident edges from $G$.

\subsection*{Bipartite Charaterization}

$G$ is \emph{bipartite} iff it has no cycles of odd length.

\subsection*{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.

\subsubsection*{Dirac Theorem}

Every graph $G$ with $|V(G)| \geq 3$ and $\delta(G) \geq \frac{n}{2}$ has a Hamiltonian cycle.

\subsection*{Eulerian Tour Condition}

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}

Bipartite $G$ with partite sets $A, B$ has a matching containing $A$ iff $\forall S \subset A : |N(S)|\geq|S|$.

\subsection*{Tutte's Theorem}

Let $q(G)$ be the number of odd components in $G$.

$G$ has perfect matching iff $\forall S \subseteq V : q(G-S) \leq |S|$.

\spacing

Any $k$-regular bipartite graph has a perfect matching and a proper $k$-edge coloring.

\subsection*{König's Theorem}

For bipartite $G$ the size of the largest matching equals the size of a smallest vertex cover.

\subsection*{Hajnal and Szemer\'{e}di}

Let $H, G$ be graphs. An \emph{$H$-factor} of $G$ is a spanning subgraph that is a set of disjoint copies of $H$ in $G$ whose vertex sets form a partition of $V(G)$.

\spacing

$\delta(G) \geq (1-\frac{1}{k})n$ for $k | n \implies G$ has a $K_k$-factor.

\section*{Connectivity}

Let $\kappa(G)$ be the \emph{connectivity} of $G$

i.e. the maximum $k$ for which $G$ is \emph{$k$-connected}.

$G$ is $k$-connected if $k-1$ vertices can be removed without disconnecting.

Let $\kappa'(G)$ be the edge-connectivity of $G$:

\vspace*{-3mm}
\[ \kappa(G) \leq \kappa'(G) \leq \delta(G) \]

\subsection*{Menger's Theorem}

For $A,B \subseteq V(G)$ the min \#vertices separating $A, B$ equals the max number of disjoint $A$-$B$-paths.

For $a, b \in V(G)$ s.t. $\{a,b\} \notin E(G)$ the minimum number of $v \in V(G)\setminus\{a,b\}$ separating $a, b$ equals the maximum number of independent $a$-$b$-paths.

\subsubsection*{Global Menger's Theorem}

Graph $G$ is $k$-connected iff $\forall a,b \in V(G)$ there exist $k$ independent $a$-$b$-paths.

\subsection*{Ear-decomposition}

Ear-decomposition of $G$ is a sequence of graphs $G_0 \subseteq G_1 \subseteq \cdots \subseteq G_k$ s.t. $G_0$ is a cycle, $G_i$ results from $G_{i-1}$ by adding an ear and $G_k = G$.

$G$ is $2$-connected iff it has an ear-decomposition.

\subsection*{Block-cut-vertex-graph}

Blocks of $G$ are the maximal $2$-connected subgraphs and bridges.

The \emph{block-cut-vertex-graph} of $G$ is the bipartite graph s.t. its partite sets are the blocks on the one side and the cut-vertices on the other side.

Block-cut-vertex-graph of connected $G$ is a tree.

\section*{Planar Graphs}

Let a \emph{plane graph} be a set of points on the plane connected by arcs s.t. the arcs do not contain any of the points or intersect any other arc.

A \emph{planar embedding} is a bijection between a plane graph and a abstract graph.
A \emph{planar graph} is a graph $G$ with a planar embedding. The corresponding plane graph is a drawing of $G$.

\subsection*{F\'{a}ry's Theorem}

Every planar graph can be embedded in a plane s.t. the edges are straight lines.

\subsection*{Euler's Formula}

For connected planar $G$ with $v$ vertices, $e$ edges and $f$ faces: $v-e+f=2$

\spacing

$|E(G)| \leq 3|V(G)|-6$ (equal if $G$ is triangulation)

$|E(G)| \leq 2|V(G)|-4$ if no face is bound by triangle.

\subsection*{Tutte's Theorem}

Every $4$-connected planar graph is Hamiltonian.

\subsection*{Graph minors}

$H$ is \emph{minor} of $G$ (i.e. $MH \subseteq G$) if it can be generated from $G$ by deleting vertices, deleting or contracting edges.

$H$ is a \emph{subdivision} of $G$ if it can be generated from $G$ by subdividing edges.

$H$ is a \emph{topological minor} of $G$ (i.e. $TH \subseteq G$) if a subgraph of $G$ is a subdivision of $H$.

\subsubsection*{Kuratowski's Theorem}

For graph $G$ the following is equivalent:

\begin{enumerate}[label=(\alph*)]
	\item $G$ is planar
	\item $K_5, K_{3,3}$ aren't minors of $G$
	\item $K_5$, $K_{3,3}$ aren't topological minors of $G$
\end{enumerate}


\section*{Colorings}

The \emph{chromatic number} $\chi(G)$ and the \emph{chromatic index} $\chi'(G)$ are defined as follows:

\vspace*{-4mm}
\begin{align*}
\chi(G) :&= \min_{k \in \N} : G \text{ has proper $k$-vertex coloring} \\
\chi'(G) :&= \min_{k \in \N} : G \text{ has proper $k$-edge coloring}
\end{align*}

$k$-regular bipartite $G$ has proper $k$-edge-coloring.

\subsection*{Cliques}

A \emph{clique} is a subgraph of $G$ that is a complete graph.
The \emph{clique number} $\omega(G)$ is the maximum order of a clique in $G$.
The \emph{co-clique number} $\alpha(G)$ is the largest order of an independent set in $G$.

\spacing

$G$ is \emph{perfect} if $\forall$ induced $H \subseteq G : \chi(H) = \omega(H)$.

Bipartite graphs are perfect with $\chi = \omega = 2$.

\subsection*{$5$-Color Theorem}

Every planar graph is $5$-colorable.

\subsection*{List coloring}

$\forall v \in V(G)$ let $L(v) \subseteq \N$ be a list of colors.

$G$ is \emph{$L$-list-colorable} if $\exists$ a proper coloring $c$ s.t. $\forall v \in V(G) : c(v) \in L(v)$.

\spacing

$G$ is \emph{$k$-list-colorable} or \emph{$k$-choosable} if it is $L$-list-colorable for all lists of $k$ colors.

\spacing

\emph{Choosability} $ch(G) := \min_{k\in\N}\{ G$ is $k$-choosable$\}$

\subsubsection*{Thomassen's $5$-List-Color Theorem}

Every planar graph is $5$-choosable.

\subsection*{Greedy chromatic number estimate}

\[ \chi(G) \leq \Delta(G)+1 \]

\subsection*{Brook's Theorem}

If $G$ is connected and neither complete nor an odd cycle then $\chi(G) \leq \Delta(G)$

\subsection*{König's Theorem}

\[ G \text{ bipartite} \implies \chi'(G) = \Delta(G) \]

\subsection*{Vizing's Theorem}

\[ \chi'(G) \in \{\Delta(G), \Delta(G)+1\} \]

\section*{Extremal Graph Theory}

For $n \in \N$ and graph $H$ the \emph{extremal number} $ex(n,H)$ is the max number of edges in a graph of order $n$ s.t. it doesn't contain subgraph $H$.

\vspace*{-3mm}
\[ ex(n,H):=\max\{\|G\| : |G|=n, H \not\subseteq G\} \]

Correspondingly $EX(n,H$ is the set of graphs on $n$ vertices and $ex(n,H)$ edges that are $H$-free.

\spacing

e.g. $ex(n,K_2) = 0, \ EX(n,K_2) = \{E_n\}, \ ex(n,P_3)=\lfloor\frac{n}{2}\rfloor$

\subsection*{Tur\'{a}n Graph}

For $1 \leq r \leq n$ the \emph{Tur\'{a}n graph} $T(n,r)$ is the unique complete $r$-partite graph of order $n$ s.t. the partite set sizes differ by at most one.

\spacing

i.e. $T(n,r)$ has $n$ mod $r$ partite sets of size $\lceil\frac{n}{r}\rceil$ and $r - (n$ mod $r)$ partite sets of size $\lfloor\frac{n}{r}\rfloor$.

$\forall v \in V(T(n,r)) : d(v) \in \{ n - \lceil\frac{n}{r}\rceil, n - \lfloor\frac{n}{r}\rfloor \}$

\spacing

$T(n,r)$ doesn't contain $K_{r+1}$ and $t(n,r) := \|T(n,r)\|$.

For $r | n \ T(n,r)$ is denoted by $K_r^s$ where $n=r \cdot s$.

\[ t(n,r) = t(n-r,r)+(n-r)(r-1)+{r \choose 2} \]

\spacing

Comparing the number of edges in $K_n$ and $T(n,r)$:

\[ \lim_{n \to \infty} \frac{t(n,r)}{{n \choose 2}} = \left( 1-\frac{1}{r} \right) \]

\subsubsection*{Tur\'{a}n's Theorem}

\[ EX(n,K_r) = \{T(n,r-1)\} \]

\subsection*{$\epsilon$-regularity}

Let $X, Y \subseteq V(G)$ be disjoint and $\|X,Y\|$ is the number of edges between $X$ and $Y$.

\[ d(X,Y) := \frac{\|X,Y\|}{|X||Y|} \text{ is the density of $(X, Y)$} \]

$\forall \epsilon > 0 : (X,Y)$ is an \emph{$\epsilon$-regular pair} if:

$\forall A \subseteq X, B \subseteq Y : \\ |A| \geq \epsilon|X| \land |B| \geq \epsilon|Y| \implies |d(X,Y) - d(A,B)| \leq \epsilon$.

\spacing

$V=V_0 \dot\cup\cdots\dot\cup V_k$ is a \emph{$\epsilon$-regular partition} if:

\begin{enumerate}
	\item $|V_0| \leq \epsilon|V|$
	\item $|V_1| = \cdots = |V_k|$
	\item At most $\epsilon k^2$ pairs $(V_i,V_j)$ for $1 \leq i < j \leq k$ are not $\epsilon$-regular
\end{enumerate}

\subsubsection*{Szemer\'{e}di's Regularity Lemma}

$\forall \epsilon > 0, m \geq 1 \exists M \in \N$ s.t. every graph $G$ with $|G| \geq m$ has $\epsilon$-regular partition $V_0 \dot\cup\cdots\dot\cup V_k$ with $m \leq k \leq M$.

\subsection*{Erd\H{o}s-Stone}

$\forall r > s \geq 1, \epsilon > 0 \exists n_0 \in \N$ s.t. all graphs with $|V(G)| =: n \geq n_0$ vertices and

\vspace*{-2mm}
\[ |E(G)| \geq t_{r-1}(n)+\epsilon n^2 \]

contain $K_r^s$ as a subgraph.

\subsection*{Asymptotic extremal number}

\[ \lim_{n \to \infty} \frac{ex(n,H)}{{n \choose 2}} = \frac{\chi(H)-2}{\chi(H)-1} \]

e.g. $ex(n,K_5 \setminus \{e\}) \simeq \frac{2}{3} \cdot {n \choose 2}$ as $\chi(K_5 \setminus \{e\}) = 4$.

\subsection*{Zarankiewicz function}

$z(m,n;s,t)$ denotes the maximum number of edges that a bipartite graph on sets of size $m$ and $n$ can have without containing $K_{s,t}$.

\subsubsection*{K\H{o}v\'{a}ri-S\'{o}s-Tur\'{a}n Theorem}

$z(m,n;s,t) \leq (s-1)^{1/t}(n-t+1)m^{1-1/t}+(t-1)m$

i.e. for $m=n$ and $t=s$:

\vspace*{-2mm}
\[ z(n,n;t,t) \in \mathcal{O}(n^{2-\frac{1}{t}}) \]

\section*{Ramsey Theory}

For $k \in \N$ the \emph{Ramsey number} $R(k) \in \N$ is the min $n$ s.t. every 2-edge-coloring of $K_n$ contains monochromatic $K_k$.

\spacing

For $k, l \in \N$ the \emph{asymmetric Ramsey number} $R(k,l)$ is the min $n$ s.t. every 2-edge-coloring of $K_n$ contains red $K_k$ or blue $K_l$.

\spacing

For graphs $G, H$ the \emph{graph Ramsey number} $R(G,H)$ is the min $n$ s.t. every 2-edge-coloring of $K_n$ contains red $G$ or blue $H$.

\spacing

For graphs $G, H$ the \emph{induced Ramsey number} $R_\text{ind}(G,H)$ is the min $n$ s.t. there is graph $F$ on $n$ vertices every 2-coloring of which contains red $G$ or blue $H$.

\spacing

For $r, l_1, \dots, l_k \in \N$ the \emph{hypergraph Ramsey number} $R_r(l_1,\dots,l_k)$ is the min $n$ s.t. for every $k$-coloring of ${[n] \choose r}$ there $\exists i \in [k], V \subseteq [n]$ with $|V|=l_i$ s.t. all sets in $V \choose r$ have color $i$.

\spacing

e.g. $R(2,k) = R(k,2) = k$ and $R(3) = 6$

\subsection*{Ramsey Theorem}

\vspace*{-2mm}
\[ \forall k \in \N : \sqrt{2}^k \leq R(k) \leq 4^k \]

Particularly Ramsey, asymmetric Ramsey and graph Ramsey numbers are finite.

\subsection*{Induced Ramsey Theorem}

$R_\text{ind}(G,H)$ is finite for all graphs $G, H$.

\subsection*{Erd\H{o}s-Szekeres' Theorem}

Any sequence of $(r-1)(s-1)+1$ distinct numbers in $\R$ contains an ascending subsequence of length $r$ or a descending subsequence of length $s$.

\subsection*{Schur's Theorem}

Let $\N$ be colored with $r \in \N$ colors.

$\implies \exists x, y, z \in \N$ of the same color s.t. $x+y=z$.

\section*{Flows}

Let $G$ be a multigraph, $T := \{(x,e,y) | xy = e \in E(G)\}$.

For abelian group $H$ the function $f : T \to H$ defines a \emph{circulation} on $G$ if:

\begin{enumerate}
	\item $\forall (x,e,y) \in T, x \neq y : f(x,e,y) = -f(y,e,x)$
	\item $\forall v \in V(G) : f(v,V) = 0$
\end{enumerate}

Let $f(X,Y) := \sum_{(x,e,y) \in T, x \neq y, x \in X, y \in Y} f(x,y)$

\spacing

For any circulation $f$ and $X \subseteq V(G)$:

$f(X,X)=0, \ f(X,V(G))=0, \ f(X,V(G) \setminus X)=0$.

\subsection*{$k$-flows}

For $k \in \N$ $f$ is a \emph{$k$-flow} if it is a $\Z$-flow s.t. $\forall (x,e,y) \in T : 0 < |f(x,e,y)| < k$.

\spacing

The smallest $k$ s.t. that $G$ has a $k$-flow $\varphi(G)$ is the \emph{flow number} of $G$.

\subsection*{Networks}

Let $s \neq t \in V(G)$ and $c : T \to \Z_{\geq0}$.

Then $(G,s,t,c)$ is a \emph{network} with \emph{source} $s$, \emph{sink} $t$ and \emph{capacity function} $c$.

\spacing

$f : T \to \R$ is a \emph{network flow} if:

\begin{enumerate}
	\item $f(x,e,y) = -f(y,e,x)$ for all $e \in E(G)$ with endpoints $x \neq y$
	\item $f(x,V(G))=0, x \in V(G) \setminus \{s,t\}$
	\item $f(x,e,y) \leq c(x,e,y)$ for all $e \in E(G)$ with endpoints $x \neq y$
\end{enumerate}

\subsubsection*{Network cuts}

$(S,\overline S)$ for $S \subseteq V(G)$ s.t. $s \in S, t \notin S, \overline S = V(G)-S$ is called a \emph{cut} in the network $(G,s,t,c)$.

\spacing

Its \emph{capacity} is $c(S,\overline S) := \sum_{x \in S, y \in \overline S, (x,e,y) \in T} c(x,y)$.

\spacing

For any flow $f$ and cut $(S,\overline S) : f(S,\overline S) = f(s,V(G))$.

\subsubsection*{Ford-Fulkerson Theorem}

In any network the maximum value of a flow equals the minimum capacity of a cut.

An integral flow $f$ with this max flow value exists.

\section*{Random Graphs}

$\mathcal{G}(n,p)$ is the probability space on graphs of order $n$ for which the edge-existence is independently decided by fixed probability $p \in [0,1]$.

This is called \emph{Erd\H{o}s-R\'{e}nyi model}.

\subsection*{Properties}

A \emph{property} $\mathcal{P}$ is a set of graphs.

$G \in \mathcal{G}(n,p_n)$ \emph{almost always} has property $\mathcal{P}$ if:

\vspace*{-2mm}
\[ \mathbb{P}(G \in \mathcal{G}(n,p_n) \cap \mathcal{P}) \to 1 (n \to \infty) \]

If $p_n$ is constant it is said that \emph{almost all} $G \in \mathcal{G}(n,p)$ have property $\mathcal{P}$.

\subsection*{Threshold functions}

$f : \N \to [0,1]$ is called \emph{threshold function} for $\mathcal{P}$ if:

\begin{enumerate}
	\item For $\frac{p_n}{f(n)} \to 0 (n \to \infty)$ graphs $G \in \mathcal{G}(n,p_n)$ almost always don't have property $\mathcal{P}$
	\item For $\frac{p_n}{f(n)} \to 1 (n \to \infty)$ graphs $G \in \mathcal{G}(n,p_n)$ almost always have property $\mathcal{P}$
\end{enumerate}

Such functions do not exist for all properties $\mathcal{P}$.

\subsection*{Simple probabilities}

Let $G$ be a graph on $n$ vertices and $m$ edges.

\vspace*{-2mm}
\[ \mathbb{P}(G = \mathcal{G}(n,p)) = p^m (1-p)^{{n \choose 2}-m} \]

\subsection*{Expected values and indicators}

Let $X : \mathcal{G}(n,p) \to \N$ be a random variable.

When $X$ counts e.g. the number of a certain class of subgraphs $\mathbb{E}(X)$ may be calculated by summing indicators over the maximum number $N$ of such subgraphs in $\mathcal{G}(n,p)$ and applying linearity:

\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) \]

\subsubsection*{Expected number of $k$-cycles}

\[ \mathbb{E}(\#k\text{-cycles in } G \in \mathcal{G}(n,p)) = \frac{n_k}{2k} \cdot p^k \]

for $n_k := n \cdot (n-1) \cdots (n-k+1)$.

\subsection*{Erd\H{o}s' lower bound on $R(k,k)$}

\[ R(k.k) \geq 2^{k/2} \]

\subsection*{Erd\H{o}s-Hajnal}

$\forall k \geq 3 \exists$ a graph $G$ s.t. $g(G), \chi(G) > k$.