Let us begin this blog entry with a handful of fairly intuitive and fun definitions.
A graph $G$ is an ordered pair $\left(V,E\right)$ of vertices $V$ and edges $E$, where $V$ is a set, and $E$ is a set containing $2$-element subsets of $V$.
For example, if $V=\left\{1,2,3,4\right\}$, and $E=\left\{\left\{1,3\right\},\left\{2,3\right\},\left\{2,4\right\}\right\}$, then $G=\left(V,E\right)$ is the following graph:
 |
| Figure 1 |
A subgraph of a graph $G=\left(V,E\right)$ is a graph $G'=\left(V',E'\right)$ where $V'\subseteq V$ and $E'\subseteq E$.
For example, the following graph:
 |
| Figure 2 |
is a subgraph of the graph in Figure 1.
A walk is a sequence $v_1,e_1,v_2,e_2,\dots,v_{n-1},e_{n-1},v_n$ of vertices $v_i$ and edges $e_i$. It can be abbreviated as: $v_1,v_2,\dots,v_n$, leaving out the edges.
A closed walk is a walk where $v_1=v_n$.
For example, the graph in Figure 1 has the following walk:
$$1,\left\{1,3\right\},3,\left\{3,2\right\},2,\left\{2,4\right\},4,\tag{$1$}$$
which is not closed since $1\neq4$.
A graph is connected if all of its vertices can be connected by one walk.
For example, the graph in Figure 1 is connected because $\left(1\right)$ is a walk that connects all of its vertices. On the other hand, the following graph:
 |
| Figure 3 |
is not connected because, say, vertex $2$ cannot be connected to, say, vertex $5$.
The degree of a vertex is the number of edges connected to it.
For example, in Figure 3, vertex $1$ has degree $1$ because edge $\left\{1,3\right\}$ is the only edge connected to it. Similarly, vertex $2$ has degree $2$ because edges $\left\{2,3\right\}$ and $\left\{2,4\right\}$ are the only edges connected to it.
An Euler cycle in a graph $G$ is a closed walk passing through all of the edges of $G$ exactly once.
For example, if we add edge $\left\{1,4\right\}$ to the graph $G$ in Figure 1, obtaining the following graph:
 |
| Figure 4 |
then
$$1,\left\{1,3\right\},3,\left\{2,3\right\},2,\left\{2,4\right\},4,\left\{1,4\right\},1\tag{$2$}$$
is an Euler cycle because it passes through all of the edges of $G$ exactly once. Note that the graph in Figure 3 cannot have an Euler cycle because it is not connected. Moreover, the following graph:
 |
| Figure 5 |
has a walk
$$4,\left\{3,4\right\},3,\left\{1,3\right\},1,\left\{1,2\right\},2,\left\{2,3\right\},3,\left\{3,4\right\},4,\tag{$3$}$$
which is closed but not an Euler cycle because it passes through edge $\left\{3,4\right\}$ more than once.
With all of that said, we have arrived at the purpose of this blog entry: proving the following theorem:
Theorem 1. If $G$ is a connected graph, then $G$ has an Euler cycle if and only if its vertices have even degree.
However, before we prove it, we must prove the following lemma:
Lemma 1. If a graph has an Euler cycle, then its vertices have even degree.
Proof. Suppose that the graph has a vertex $v$ of odd degree $d$. Then the cycle $c$ either starts or ends at $v$ or neither starts nor ends at $v$. If $c$ neither starts nor ends at $v$, then $c$ passes through $v$ via two unique edges, implying that $d\geqslant3$. Therefore, $c$ must pass through $v$ again via two new, unique edges, implying that $d\geqslant5$. Clearly, this process will never end, so $c$ must start or end at $v$. If $c$ starts or ends at $v$, then it must end or start at $v$, respectively, implying that $d\geqslant3$. Therefore, $c$ must pass through $v$, implying that $d\geqslant5$. As before, this process will never end. Hence, by contradiction, the graph has no vertex of odd degree. $\blacksquare$
We are now ready to tackle the theorem:
Proof (Theorem 1). Suppose that $G$ has an Euler cycle. Then, by Lemma 1, the vertices of $G$ have even degree. Conversely, suppose that the vertices of $G$ have even degree, pick any vertex $v_0$, and create a closed walk $v_0,v_1,\dots,v_n=v_0$ that passes through all of the edges connected to $v_0$ and that passes through all of its edges exactly once (convince yourself that this is possible). We will proceed by induction. If the walk passes through all of the edges of $G$, then we are done. Otherwise, consider the subgraph of $G$ obtained by removing the vertex $v_0$ and by removing all of the edges of $G$ that are in the walk. Then the resulting subgraph comprises a further set of subgraphs $G_1,\dots,G_k$ whose vertices have even degree. By the induction hypothesis, each $G_i$ has an Euler cycle, call it $v_{i,1},v_{i,2},\dots,v_{i,n_i}=v_{i,1}$. Finally,
$$\begin{align}&v_0,v_1,\dots,v_{1,1},v_{1,2},\dots,v_{1,n_1}=v_{1,1},\\&v_{1,n_1+1},\dots,v_{2,1},v_{2,2},\dots,v_{2,n_2}=v_{2,1},\\&v_{2,n_2+1},\dots,v_{k,1},v_{k,2},\dots,v_{k,n_k}=v_{k,1},\\&v_{k,n_k+1},\dots,v_n=v_0.\end{align}$$
is an Euler cycle (we assume WLOG that $v_{i,1}$ comes before $v_{i+1,1}$ in the walk). $\blacksquare$
This answers a question that Leonhard Euler asked in 1736.