\problemdata     
{graphs-2}           
{graphs, vertex degree}              
{}              
{S02 in-class W4}
{}


\begin{problem}

Let $G$ be a graph with $n$ vertices and $m$ edges. Let $dmax$ be the
maximum degree of the vertices of $G$, and let $dmin$ be the minimum
degree of the vertices of $G$. Show that
\begin{problemparts}
\problempart $2m/n \geq dmin$.

\solution{We want to show that $2m \geq n\cdot dmin$. Observe that $2m$
is the sum of the degrees of all the vertices (each of the $m$ edges
adds 2 to the total sum since it increases the degree of each of its
two incident vertices by 1). The sum of the $n$ degrees cannot be less
than $n$ times the minimum degree. In other words,  $2m \geq n \cdot
dmin \implies 2m/n \geq dmin$.  

}

\problempart $2m/n \leq dmax$.

\solution{Similarly, the sum of the $n$ degrees cannot be greater
than $n$ times the maximum degree. So,  $2m \leq n \cdot
dmax \implies  2m/n \leq dmax$.
}

\end{problemparts}
\end{problem}
