In-degree and Out-degree

How many edges touch each vertex? That's what degree measures, and it's the
single most useful local property of a graph.

Definition 6.1.3 (notes p. 83) defines the degree functions. For a directed
graph $G = \langle V, E \rangle$ and a vertex $v \in V$:

- In-degree counts the edges coming into $v$:

For an undirected graph, an edge $\{w, v\}$ is incident to both $w$ and $v$, so we
typically just say "degree" and $\text{indeg}(v) = \text{outdeg}(v)$.

A useful sanity check is the handshaking lemma for undirected graphs:

Every edge contributes 1 to the degree of each of its two endpoints — so it is
counted twice when we sum degrees. This gives us a quick way to bound the number
of edges from the sum of degrees.

Sources and sinks are special cases (Definition 6.1.6):
- A source has $\text{indeg}(v) = 0$ (no edges point in).
- A sink has $\text{outdeg}(v) = 0$ (no edges point out).

Every DAG must have at least one source — we will see this when we study DAGs.