A Universe of Sorts

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}

§ Linear Algebraic Proof of the Handshaking Lemma

§ A simplification from arjun