Let $G$ be a simple graph on $n$ vertices $v_1,v_2...v_n$. Let $G-v_i$ is having $m_i$ edges for $1\leq i \leq n$. Then prove that $m=\frac{1}{n-2}\sum_{i=1}^{n}m_i$.
1
-
$\begingroup$ Welcome to MSE. It will be more likely that you will get an answer if you show us that you made an effort. $\endgroup$ – José Carlos Santos Jan 26 '18 at 15:27
1
$\begingroup$
$\endgroup$
By handshake lemma we have $$\sum _{i=1}^n d_i = 2m$$
For each $i$ we have $$m_i = m-d_i$$ where $d_i$ is degree of $i$-th node. Now if we sum this over all $i$ we get
$$ \sum _{i=1}^n m_i = n\cdot m -\sum _{i=1}^n d_i = nm -2m = m(n-2)$$
and we are done.