I am currently learning Graph Theory and I've decided to prove the Handshake Theorem which states that for all undirected graph,
$$\sum_{u\in V}\deg(u) = 2|E|\ .$$
At first I thought the theorem is very intuitive so proving it would be easy. But then I've realized that my intuition to the theorem cannot be translated to the writing of the proof; describing how it works is easier than formalizing it into a series of logical steps that would prove the theorem. Anyway, I've tried my best but I think my proof is very clunky and too verbose so I want to ask if it is correct or maybe suggestions on writing proof in general.
Proof
Let $G = (V,E)$ be an undirected graph. We want to count the sum of the degree of vertices of $G$ so, for the sake of proving an argument, we let $$\sum_{u\in V}\deg(u) = 0 \ ,$$ i.e. we set the degree of all vertices to zero and only then will we increment the $\deg(u)$ if $u$ is incident to $e_i \in E$.
Let $e_1$ be the first edge we choose. $e_1$ is incident to $v_j,v_k \in V$ and hence we increment each of their degree by one, so $\deg(v_j) = 1 = \deg(v_k)$. Note that if $v_j = v_k$, i.e. $e_1$ is incident to only one vertex (often called a 'loop'), then the degree of that vertex would be incremented by two. For $m = |E|$, we do the same process to $e_2, e_3,\dots,e_m$, incrementing the degree of the vertices incident to an edge. We will notice that for every edge, we increment the total degree of $V $ (or $ \sum_{u\in V}\deg(u)$) by two and since there are $m$ edges, we incremented the initially zero-valued total degree of $V$ by $2m = 2|E|$.
Hence,
$$\sum_{u\in V}\deg(u) = 2|E|$$
is proved to be true. $\ \blacksquare$
$\endgroup$ 22 Answers
$\begingroup$As you mentioned, the difficulty in proving this formally is that we humans intuitively "see" the bijection needed. The arguing of user598858 will be accepted in most cases, but if you look for a more formal proof, I'll give you one.
First assign an orientation to $G$, i.e. make each edge directed, i.e. assign two functions $s,t:E\rightarrow V$ such that vertices $v$ and $w$ are adjacent if and only if there is an edge $e$ such that ($s(e)=v$ and $t(e)=w$) or ($s(e)=w$ and $t(e)=v$). If $E$ is a subset of the two-element-sets of $V$ in your definition, this is equal to $e=\{s(e),t(e)\}$.
Let $\mathcal P(X)$ denote the power set of a set $X$. Next we define $O:V\rightarrow\mathcal P(E\times\{0\})$ by $O(v) := \{(e,0): s(e)=v\}$ and $I:V\rightarrow\mathcal P(E\times\{1\})$ by $I(v) := \{(e,1): t(e)=v\}$. Observe that $O(v)$ represents all edges starting in $v$ and $I(v)$ represents all edges ending in $v$, so especially we have for a loop $\ell$ in $v$ that $(\ell,0)\in O(v)$ and $(\ell,1)\in I(v)$, i.e. loops are in both the outgoing and the incoming edges. So we observe that $$\operatorname{deg}(v)=|O(v)\cup I(v)|=|O(v)|+|I(v)|,$$ since $O$ and $I$ were designed to be disjoint.
Now observe that for any vertices $v,w$ with $v\neq w$ we have $I(v),O(v),I(w),O(w)$ all mutually disjoint. Proof: Again the disjointness of $I$ and $O$ is clear because of the second coordinate. Assume that $(e,0)\in O(v)\cap O(w)$, then by definition we have $v=s(e)=w$, a contradiction, so $O(v)$ and $O(w)$ are disjoint. Analogue reasoning shows that $I(v)$ and $I(w)$ are disjoint.
Since they are mutually disjoint, we have$$\begin{aligned} \left|\bigcup_{v\in V} O(v)\right| &= \sum_{v \in V} |O(v)|\\ \left|\bigcup_{v\in V} I(v)\right| &= \sum_{v \in V} |I(v)| \end{aligned}$$
Next we have$$\begin{aligned} E\times\{0\} &= \bigcup_{v\in V} O(v) \\ E\times\{1\} &= \bigcup_{v\in V} I(v) \end{aligned}$$"$\subseteq$": Simply because by $s$ and $t$ an edge $e$ gets assigned to (only) $O(s(e))$ and (only) $I(t(e))$. "$\supseteq$": Since $O(v)\subseteq E\times\{0\}$ for any vertex $v$, the same holds for their union. Analogue with $I(v)\subseteq E\times\{1\}$.
We conclude$$\begin{aligned} 2|E|&=|E\times\{0\}|+|E\times\{1\}| \\ &= \left|\bigcup_{v\in V} O(v)\right| + \left|\bigcup_{v\in V} I(v)\right| \\ &= \sum_{v \in V} |O(v)| + \sum_{v \in V} |I(v)| \\ &= \sum_{v \in V} |O(v)\cup I(v)| \\ &= \sum_{v\in V} \operatorname{deg}(v) \end{aligned}$$
$\endgroup$ $\begingroup$One line proof: Each edge gives one degree to its each end points and for a loop on a vertex, it provides $2$ degree to the vertex so $2\times |E|= \text{degree sum}$.
$\endgroup$
