§ Linear algebraic proof of the handshaking lemma
We wish to show that the number odd vertices is even. Let be the adjacency
matrix of the undirected graph . Since is undirected, . Now
move everything to , including . This means that has entries .
Now, denote the vector of all ones by . See that
counts the partities of the degrees of each vertex, and counts the
sum of parities of the degrees of each vertex.
Note that the vertices of even degree with add to the sum , while
odd vertices will add a . Thus, 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 .
We will now algebraically simplify (does anyone have a cleaner proof?)
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 , we have that for lower triangular.
This allows us to simplify: