Number of edges and degree in a simple graph

120 Views Asked by At

For a Simple Graph G with vertices $v_{1},v_{2},.....,v_{n}$ , $n \geq 3$

Given Proposition $\Rightarrow$

$e \left(G \right)$=$\frac{\sum e \left(G -v_{i}\right)}{n-2}$

and

$d_{G} \left(v_{i} \right)$=$\frac{\sum e \left(G -v_{i}\right)}{n-2} - e \left (G-v_{j} \right) $

Explanation -:

An edge of $G$ appears in $G-v_{i}$ if and only if v_{i} is not endpoint of e.(i got this point ). Thus $ \sum \left (G-v_{i} \right )$ counts each edge exactly $n-2$ times.

i am not getting this point and so is the 1st equation.

Furthur its explained that once we know $e \left(G \right)$ ,the degree of $v_{i}$ can be computed as the number of edges lost when deleting $ v _{i}$ to form $G -v_{j}$ and hence 2nd eqtn proved .....not getting this too..

1

There are 1 best solutions below

7
On BEST ANSWER

Suppose for a moment that we know that

$$e(G)=\frac{\sum_ie(G-v_i)}{n-2}\;.\tag{1}$$

There are $e(G)$ edges in $G$. Removing $v_j$ from $G$ removes only the edges of $G$ that have $v_j$ as an endpoint, and there are $\deg_G(v_j)$ of those. Thus, the number of edges in $G-v_j$ must be $e(G)-\deg_G(v_j)$, i.e., $e(G-v_j)=e(G)-\deg_G(v_j)$. Rearranging this and substituting the known value of $e(G)$ from $(1)$ gives us the result that

$$\deg_G(v_j)=e(G)-e(G-v_j)=\frac{\sum_ie(G-v_i)}{n-2}-e(G-v_j)\;.$$

Now let’s get back to $(1)$. For each vertex $v_i$ of $G$ we know that $e(G-v_i)=e(G)-\deg_G(v_i)$, so

$$\begin{align*} \sum_{i=1}^ne(G-v_i)&=\sum_{i=1}^n\big(e(G)-\deg_G(v_i)\big)\\ &=\sum_{i=1}^ne(G)-\sum_{i=1}^n\deg_G(v_i)\\ &=ne(G)-\sum_{i=1}^n\deg_G(v_i)\\ &=ne(G)-2e(G)\\ &=(n-2)e(G)\;, \end{align*}$$

and $(1)$ follows immediately