<aside> 💡 Def.
The degree of a vertex is the number of edge ends that it is involved with.
</aside>
This is almost counting edges, but loops count twice.
In a simple graph ( no parallel edges), the degree of $\nu$ is equal to $|N(\nu)|$,
Notationally, we can write $deg(\nu)$.
<aside> 💡 Thrm.(Handshake Theorem)
In an undirected graph with $m$ edges:
$$ 2m=\sum_{v\in V}deg(v) $$
Proof:
count ends of edges, either by looking at edges or neighbourhoods of vertices.
</aside>
<aside> 💡 Thrm.
Every graph has an even number of vertices with odd degree.
Ex.
In out example, there are 2 vertices with odd degree ($v$ and $w$) and $2$ is even.
Proof:
Let $V_e$ be the set of vertices with even degree, and $V_o$ be the set of vertices with odd degree.
We know $2m=\sum_{v\in V}deg(v)=\sum_{v\in V_e}deg(v)+\sum_{v\in V_o}deg(v)$.
If we take remainders upon division by $2$, the $LHS$ has remainder zero.
The terms in the first sum each have remainder zero.
Each term is the second sum has remainder one.
So module $2$, we have $0\equiv 0+|V_o|$ or $|V_o|$ is even.
$$ \hspace{2in} Q.E.D $$
</aside>
In a directed graph, instead of degrees, vertices have
in-degrees: $deg^-(v)= \#$ of edges with $v$ as the destination.
and out-degrees: $deg^+(v)= \#$ of edges with $v$ as the source.
$$ |E|=6=3+1+1+1=0+2+3+1 $$
$$ deg^+(u)=3\ ，deg^-(u)=0\\ deg^+(v)=1\ ，deg^-(v)=2\\ deg^+(w)=1\ ，deg^-(w)=3\\ $$
<aside> 💡 $P_n$ is a path of length $n$(= # of degrees. )
</aside>
is $P_4$
<aside> 💡 $C_n$ is a cycle of legnth $n$.
</aside>
Ex.
$C_3$
$C_4$
$C_5$
The vertices are $\{v_1,v_2,v_3,…,v_n\}$
and $v_i$ is adjacent(é‚») to $v_j$ if $|i-j|=1$ or $\{i,j\}=\{1,n\}$
[…]
<aside> 💡 $K_n$ = the complete graph with $n$ vertices.
(There are $n$ vertices, and every pairs are adjacent)
</aside>
Ex.
$K_1$
$K_3$
$K_2$
$K_4$
$K_5$ cannot be drawn without crossing edges.
