===== Vertex degree =====
==== Function ====
| @#55CCEE: context     | @#55CCEE: $G=\langle V,E,\psi\rangle$ ... undirected graph |

| @#FFBB00: definiendum | @#FFBB00: $ \mathrm{dom}\ d = V $ |

| @#DDDDDD: range       | @#DDDDDD: $ u,v\in V, u\neq v $ |
| @#DDDDDD: range       | @#DDDDDD: $ e\in E $ |

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

==== Discussion ====
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.
=== Theorems ===
  * 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

  * For a simple graph, if $A$ is the [[adjacency matrix]], then 

$\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]].

==== Parents ====
=== Context ===
[[Undirected graph]]
[[Set cardinality]]