701 views
0 votes
0 votes

How S2 is correct ,I can have more than n-k edges like if n=7 and k=3 ,then K1(a-b-c-d-e) k2(f() k2(g).K1,k2,k3 are different compoinents i assumes,Now in K1 i can add one more edge between a to c or a to d and still it will be simple graph and it will have 3 components?Please help

1 Answer

0 votes
0 votes

Assuming a graph $G$ has $K$ component.

$C_1,C_2,C_3,\dots,C_k$

Then,

  1. $\bf n_i$ = no of vertices in $C_i$
  2. $C_i$ component can have a minimum of $E_i(C_i)$ = $\bf n_i-1$ edges. (as in a tree)
  3. If total vertices in $G$ = $N$, Then,
  4. $\begin{align*} E(G) = \sum_{i=1}^{K}\left [ E_i(C_i) \right ] = \sum_{i=1}^{K}\left ( \bf n_i-1 \right ) = N-K \end{align*}$ 

Related questions

1 votes
1 votes
1 answer
1
0 votes
0 votes
0 answers
2
3 votes
3 votes
0 answers
3