1
$\begingroup$

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$.

$\endgroup$
  • $\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$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.