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




\begin{problem}
Prove that in any undirected graph, the sum of the squares of
the vertex degrees is even, or provide a counterexample.
\end{problem}
\solution{The assertion is true. 

{\em Proof 1}

Let $V_e$ be the set of even degree vertices and $V_o$ the set of odd
degree vertices of the graph.  From class we know that there is an
even number of odd degree vertices. So can write

\begin{equation}\label{eq3}
\sum_{v \in V} deg(v)^2 = 
\sum_{v \in V_e} deg(v)^2 + \sum_{v \in V_o} deg(v)^2
\end{equation}

If $v \in V_e$ then $deg(v)$ is even, hence $deg(v)^2$ is also even.
Therefore, the first term in the right hand side of (\ref{eq3}) is
even.  Similarly if $v \in V_o$, then $deg(v)^2$ is odd.  The second
term in the right hand side is a sum of odd numbers with an even
number of terms.  Therefore it is also even.  We conclude that
$\sum_{v \in V} deg(v)^2$ is even

{\em Proof 2}

Let $E$ be the set of edges of the graph and
$V = \{ v_1, \ldots , v_n \}$ be the set of vertices of the graph.

\begin{equation}\label{eq1}
(\sum_{i=1}^n deg(v_i))^2 = \sum_{i=1}^n deg(v_i)^2 +
2 \sum_{i \neq j} deg(v_i) deg(v_j)
\end{equation}

The left hand side of (\ref{eq1}) is even because $ \sum_{i=1}^n
deg(v_i) = 2|E|$ and the second part of the right hand side is
obviously even.  Therefore $\sum_{i=1}^n deg(v_i)^2$ is even. 
}