> [!NOTE] Theorem (...) > In any [[Directed Graph|undirected]] graph with at least two vertices, there must be two vertices with the same degree. >*Proof*. Suppose the graph has vertices $v_{1},\dots,v_{n}$ and consider the function $f:\{ v_{1},\dots,v_{n} \}\to \{ 0,1,\dots,n-1 \}$ that gives the number of friends for each person in the group. >If the claim is false then $f$ is injective, implying that there exists $i,j$ such that $f(v_{i})=0$ and $f(g_{j})=n-1$, a contradiction since edges are undirected. > >Similar to that of [[Pigeonhole Principle#^6a4b80|pigeonhole principle 1]].