Graph theorem(homework) This is the theorem If $G$ is a graph, there are at least $2$ vertices(points ) always have the same degree. e.g: I have graph $G$, $(U,V)$ ,$4$ vertices $(e1,e2,e3,e4)$ ,and $4$ edges. So the degree we have $(2,2,2,2)$, and if i put one vertice ,and obtain new graph or new vertice, and so on the graph always have a same degree ,at least $2$ .. How i can proof it with pigeon hole principle or others? Can you give me a clu?

**Hint:**

* This is true only in simple graphs (no loops or multiple edges).
* Consider some connected component and denote its size by $n$.
* There are $n$ vertices, but only $n-1$ possible degrees.



I hope this helps $\ddot\smile$