Vertex degree

context

$G=\langle V,E,\psi\rangle$ … undirected graph

definiendum

$\mathrm{dom}\ d = V$

range	$u,v\in V, u\neq v$
range	$e\in E$

definiendum

$d(v):=\left|\{e\ |\ \exists u.\ \psi(e)=\{u,v\}\}+2\ \mathrm{card} \{e\ |\ \psi(e)=\{v,v\}\}\right|$

The value $d_G(v)$ is the number of neighbours of $v$ with loops counted twice.

It is also equal to the sum over the $v$ -row or $v$ -column of the adjacency matrix of the graph.

Because each edge connects two vertices, the number of vertices with odd degree is even, and then so is the sum over all degrees. I.e.

$\left| \{v\ |\ d(v)...\mathrm{odd}\} \right|$ … even

$\sum_{v\in V}d(v)$ … even

$\mathrm{tr}\ A^2=\sum_k(\sum_i A_i^k A_k^i)=\sum_i(\sum_k \delta_{i\ \mathrm{connected\ to }\ k})=d(v_i)$

This also works with $MM^t$ , where $M$ is the incidence matrix.