## § Linear algebraic proof of the handshaking lemma

We wish to show that the number odd vertices is even. Let $A$ be the adjacency matrix of the undirected graph $G$. Since $G$ is undirected, $A = A^T$. Now move everything to $F_2$, including $A$. This means that $A$ has entries $\{0, 1\}$. Now, denote the vector of all ones by $o \equiv (1, 1, \dots 1)$. See that $Ao$ counts the partities of the degrees of each vertex, and $o^T(Ao)$ counts the sum of parities of the degrees of each vertex. Note that the vertices of even degree with add $0$ to the sum $o^TAo$, while odd vertices will add a $1$. Thus, $o^TAo$ will equal the parity of the number of odd vertices. As we wish to show that the number of odd vertices is even, we want to prove that $o^TAo = 0$. We will now algebraically simplify $o^TAo$ (does anyone have a cleaner proof?) giving us:
\begin{aligned} &o^TAo = \sum_{ij} o_i A_{ij} o_j \\ &= \sum_{i=j} o_i A_{ij} o_j + \sum_{i < j} o_i A_{ij} o_j + o_j A_{ji} o_i \\ &\text{(A is symmetric; A_{ji} = A_{ij})} \\ &= \sum_{i=j} o_i A_{ij} o_j + \sum_{i < j} o_i A_{ij} o_j + o_j A_{ij} o_i \\ &= \sum_{i=j} o_i A_{ij} o_j + \sum_{i < j} 2 \cdot o_i A_{ij} o_j \\ &\text{(F_2 has characteristic zero, so 2 = 0)} \\ &= \sum_{i=j} o_i A_{ij} o_j + 0 \\ &\text{(replace i = j with k)} \\ &= \sum_{k} o_k A_{kk} o_k \\ &\text{(A_{kk} = 0 since graph has no self loops)} \\ &= \sum_{k} 0 \cdot o_k^2 = 0 \end{aligned}
So, the number of vertices of odd degree is even. I want to avoid this computation with respect to the basis, but I'm not sure how to do that.

#### § A simplification from arjun

Since $A_{kk} = 0$, we have that $A = B + B^T$ for $B$ lower triangular. This allows us to simplify:
\begin{aligned} & o^T A o = o^T (B + B^T) o = \\ & =o^T B o + o^T B^T o = \langle o, Bo \rangle + \langle Bo, o \rangle \\ & = 2 \cdot \langle o, Bo \rangle = 0 \end{aligned}