\part{Fundamentals}

\chapter{Graphs}

In the Prussian town of Königsberg (today the Russian town of Kalingrad), there were 7 bridges connecting 4 distinct sides of the town.
Is it possible to walk a path between these 'islands' that traverses each bridge exactly once?

This problem is hailed as the birth of 2 different fields; graph theory and topology.

Graph theory concerns itself with discrete (finite or countable).It allowed Euler to reduce the Konigsberg problem to its most rudimentary elements and examine how the bridges connect the islands. Due to its discrete nature, it is intimately related to combinatorics as it not only borrows combinatorial arguments to prove statements about graphs, but employs graphs as a structure to produce combinatorial results!


One basic but elegant example of graph theory providing a combinatorial result that affects number theory is by double-counting the edges of complete graphs to combinatorially prove that $\sum^{n}_{k=1} k = \frac{n(n+1)}{2}$! We will go through this when sufficient theory is developed.


Topology extends its focus to more general spaces . It is actually possible to analyze graphs as topological spaces, however with topology being a more general theory, many concepts arising from their discrete structure are better studied from a graph theoretic point of view. THat said, topology can still capture many concepts related to graphs, and if one wants to consider the space on which a graph label is embedded upon (such as in the 3 utilities problem), topology becomes a requirement.

Aside from combinatorics and topology, probability theory borrows graphs as structures to discuss discrete Markov chains. Indeed, the power of graph theory permeates itself into applications of mathematics, being central in the field of computer science, and being commonplace in the fields of electrical engineering, chemistry, and mathematical optimization.

\section{Undirected graphs}

This part aims to introduce the fundamentals of graph theory by studying undirected graphs first. The construction relies heavily on the machinery of set theory.

Graph theory is notable for having an abundance of terminology, however the concepts behind them are generally simple.


\begin{definition}[Undirected graph]
An \emph{undirected graph} $G$ is a 3-tuple $(V,E,\varphi)$ as specified by the following.
\begin{itemize}
\item $V$ is a set, its elements are called \emph{vertexes}
\item $E$ is a set, its elements are called \emph{edges}
\item $\varphi : E \to \{ \{v_1,v_2\} : v_1 , v_2 \in V \}$ is a set mapping edges to multisets of 2 vertexes.
\end{itemize}
\end{definition}


The intuition for graphs is that a vertex is some node and the edges represent connetions between different (or even the same) node.
Drawing them. The definition of graph is completely distinct of its label. Topological graph theory notably characterizes some of the phenomena one observes when physically drawng a graph,such as crossing edges.



\begin{definition}[Undirected subgraph]
A \emph{subgraph of $G$} is an undirected graph $H$ with the came incidence function thatalso satisfies the following.
\begin{itemize}
\item $V_{H} \subseteq V_{G}$
\item $E_{H} \subseteq E_{G}$
\item $\varphi : E \to \{ \{v_1,v_2\} : v_1 , v_2 \in V \}$ is a set mapping edges to multisets of 2 vertexes.
\end{itemize}
$(V_{H},E_{H},\varphi) \leq (V_{G},E_{G},\varphi) $
\end{definition}


Complete graphs
The \emph{$n$-complete graph} is the undirected, simple graph not permitting loops $K_n=(V,E,\varphi)$  where every vertex is connected to eachother.
\begin{itemize}
	\item $|V|= n$
	\item $|E|= \frac{n(n-1)}{2}$
	\item $\varphi$ is bijective
\end{itemize}

\section{Loops}


We remind you that a multiset is just a set where the same element may appear multiple times.

\begin{definition}[Simple graph]
An \emph{simple graph} is a graph such that its incidence function $\varphi$ is injective, otherwise it is called a \emph{multigraph}.
\end{definition}

\begin{definition}[Loop]
A \emph{loop} is an edge mapped by the incidence function to some multiset of the form $\{v_1 ,v_1\}$ (i.e it has a 2-multiplicity element).
\end{definition}

\begin{definition}[Graph permitting loops]
A \emph{graph permitting loops} is a graph that has a loop
\end{definition}

\section{Directed graphs}

Now that we understand the general jist of graph theory, we can start to study some more exotic graphs.

\begin{definition}[Directed graph]
An \emph{directed graph} $G$ is a 3-tuple $(V,E,\varphi)$ as specified by the following.
\begin{itemize}
\item $V$ is a set, its elements are called \emph{vertexes}
\item $E$ is a set, its elements are called \emph{edges}
\item $\varphi : E \to \{ (v_1,v_2) : v_1 , v_2 \in V \}$ is a set mapping edges to ordered pairs of 2 vertexes.
\end{itemize}
\end{definition}

natural number weights
integer weights
real weights
nonnegative real weights
inclusion of $\pm\infty$ weights

\section{Weighted graphs}
\begin{definition}[Weighted graph]
A \emph{weighted graph} $G$ is a 2-tuple $(G,d)$ as specified by the following.
\begin{itemize}
\item $G$ is a graph (directed or undirected)
\item $w : E_G \to [0,\infty)\cup\{\infty\}$ is a distance function
\end{itemize}
\end{definition}


we have a way to allocate weight to edges, however if we orient ourselves with the goal of finding the path of least cost, we are inspired to develop the distance function.

distance function

\[d(v_1,v_2) = \min \{ w(e) : e \in \varphi^{-1}(\{v_1,v_2\}) \} \]
\[d(v_1,v_2) = \min \{ w(e) : e \in \varphi^{-1}(\{v_1,v_2\}) \} \]

\[d(v,v) = 0 \]
\[d(v_1,v_2) + d(v_2,v_3) \geq d(v_1,v_3) \]

in an undirected graph
\[d(v_1,v_2) = d(v_1,v_2) \]


An interesting problem in the realm of computer science is to find the least costly path between 2 given vertexes. There are various algorithms that provide a solution to this problem with different runtimes, and they are employed in many networking protocols that we implicitly use today!



\section{Graph isomorphsim}


\begin{definition}[Graph isomorphism]
bijective function $f : V_G \to V_H$ such that  $v_1,v_2$ are adjacent in $G$ iff $f(v_1),f(v_2)$ are adjacent in $H$. We say $G \cong H$
\end{definition}

A big open problem in mathematics and computer science is finding an polynomial time algorithm that can verify whether two undirected graphs are isomorphic.

Graph isomorphisms mean that not only are graphs independent of their labelled graph, but the vertexes may be assigned any symbols; we often like to use the natural numbers.



\chapter{Features of graphs}

\section{Degree}


\begin{definition}[Degree of a vertex]
	\[\mathrm{deg}(v) = |\{e \in E : v \in \varphi(\{e\})\}| + |\{e \in E : e \in \varphi^{-1}(\{v,v\})\}|\]
\end{definition}

An important combinatorial result follows the theory of degrees.
\begin{lemma}[Handshaking lemma]
Let $(V,E,\varphi)$ be an undirected graph permitting loops, then the following equality holds.
\[\sum_{v \in V} \mathrm{deg}(v) = 2|E|\]
\end{lemma}




\section{Graph matrixes}

Thanks to graph isomorphism, we can assume our graph is 


\begin{definition}[Adjacency matrix]
Let $G=(\mathbb{N}\cap[1,n],E,\varphi)$ be a graph, the \emph{adjacency matrix of $G$} is the following symmetric matrix.
	\[\mathbf{A}_{ij} = \begin{cases} 1 & \varphi^{-1}(\{\{i,j\}\}) \subseteq E \\ 0 \varphi^{-1}(\{\{i,j\}\})\cap E=\emptyset \end{cases}\]
\end{definition}

Notice that for undirected graphs the adjacency matrix is a symmetric matrix.

\begin{definition}[Degree matrix]
Let $G=(\mathbb{N}\cap[1,n],E)$ be a graph, the \emph{degree matrix of $G$} is the following diagonal matrix (note the use of the Kronecker delta).
\[\mathbf{D}_{ij} = \mathrm{deg}(i) \delta_{ij}\]
\end{definition}

\section{Paths}
- path

A \emph{walk} is a sequence of edges $(e_i)$ such that $\phi $
A \emph{trail} is a walk of distinct edges.
A \emph{path} is a trail of distinct vertexes.

A Hamiltonian path is a path that visits all vertexes exactly once.
An Eulerian trail is a trail that visits all edges exactly once.


\subsection{Connected graphs}
Paths allow us to form the notion of a connected graph


\begin{definition}[Connected graph]
A \emph{connected graph} is a graph such that there exists a path between each pair of vertexes.
\end{definition}

Topology students may note that the notion of a path connected topological space is extremely similar in spirit to the connected graph; vertexes are ananalogous to points, and the topological and graphical paths used are analogous, however defined for completely different settings.



\subsection{Kőnig's lemma}


Connected graphs will be a frequent point of discussion in our study of graph theory, however it is worth a detour to discuss a rather fun result on infinite connected graphs.
\begin{definition}[Infinite graph]
A \emph{locally finite graph} is a graph with infinite vertexes.
\[|V| \geq \aleph_0\]
\end{definition}

\begin{definition}[Locally finite graph]
A \emph{locally finite graph} is a graph where every vertex has a finite degree.
\[\mathrm{deg}(v) < \infty\]
\end{definition}

\begin{lemma}[Kőnig's lemma]
Let $G$ be a connected, infinite, locally finite undirected graph, then $G$ has an infinite simple path.
\end{lemma}

\begin{corollary}
Let $G$ be a connected, infinite, undirected graph, if $G$ has no infinite simple path then it has a vertex with infinite degree.
%\[G \text{ is a connected, infinite, undirected graph } \land G \text{ has no infinite simple path} \exists v [ \mathrm{deg}(v) \geq \aleph_0 \]
\end{corollary}

\section{Cycles}

An object that is similar in nature to a path is a cycle; these 'loop' in the sense that the final vertex is also the first.
- cycle
- Hamiltonian cycle
- Eulerian cycle
\section{Trees}

A computer scientist's best friend is a tree (no wonder they're so lonely).

\begin{definition}[Tree]
A \emph{tree} is a connected, acyclic, undirected graph.
\end{definition}

\begin{definition}[Binary tree]
Tree where vertexeshave a maximum degree of 3.
\end{definition}


\begin{definition}[Spanning tree]
subgraph that is a tree
\end{definition}


\subsection{Propositions on trees}
\begin{proposition}
Let $(V,E,\varphi)$ be a tree, then the following equation holds.
\[|V|=|E|+1\]
\end{proposition}

\begin{proposition}
Let $(V,E,\varphi)$ be a complete binary tree, then its height is $ \lfloor \log_{2}(|V|) \rfloor$
\end{proposition}

\begin{proposition}
Let $(V,E,\varphi)$ be a complete binary tree, then its height is $ \lfloor \log_{2}(|V|) \rfloor$
\end{proposition}

\subsection{Cayley's formula}
\begin{proposition}[Cayley's formula]
There exists $n^{n-2}$ trees with $n$ vertexes.
\[|\{ G=(V,E,\varphi) : G \text{ is a tree} \land |V|=n \}| =n^{n-2}\]
\end{proposition}

\section{Directed acyclic graph}
- directed acyclic graph (DAG)


\chapter{Euler's formula}


As previously stated, graph theory and topology were born out of the same problem, and hence are intimately connected. One major area of topological graph theory is studying the consequences of drawing graph labels on surfaces with different properties (a plane, torus, 'book' etc.). 

This chapter will give an elementary result of topological graph theory related to the plane (i.e drawing, or in topological terms, embedding graph labels on a piece of flat paper) and allude to how topological properties of graphs can change when embedded into different spaces. The result that all of our observations will orbit around is the magnificent Euler's formula (as if he doens't have enough formulae already).


\section{3 Utilities problem}

We first study a classical problem that gave birth to topological graph theory.

\section{Euler's formula}

\begin{theorem}[Euler's formula (Planar case)]
Let $(V,E,\varphi)$ be a connected undirected graph and $F$ be the amount of distinct faces partitioned by the graph label's edges, then the following equation holds.
\[|V|-|E|+F=2\]
\end{theorem}

\section{Solving the 3 utilities problem}

Using this formula, we can see that the 3 utilities problem cannot be solved since

However there's an implicit assumption we've been using all along; our graph lies upon a plane! If we consider graphs on different surfaces (such as a torus) the 3 utilites problem does in fact have a solution. This means that other surfaces require their own versions of Eucler's formula; as it turns out, the right hand side is what changes depending on the surface, this number is something called the \emph{Euler characteristic}. This is covered as a topic within algebraic topology.

Not only does topological graph theory study the topologies formed by different graphs, but also the effects of defining graphs on different topologies!
Now we have an understanding of what it means to study graphs on different topologies, however