\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