Esto es lo que llevo:
Supongamos \( H \) es un árbol (componente conexa de un bosque). Veamos que \( e_h=v_h-1 \).
Por inducción sobre el numero de vértices:
a) Si \( v_h=1 \), es claro que \( e_h=v_h-1=0 \)
b) Supongamos que la hipótesis se verifica para \( k\geq{1} \). Probemos que se cumple para k+1.
Sea entonces I un árbol con n+1 vértices. Es posible encontrar un vértice terminal (con indice de grado 1) (*). Si lo retiramos queda un bosque conexo J de n vértices y un lado menos que I. Por hipótesis, \( e_j=v_j-1 \) por lo tanto, \( e_I=e_j+1=v_j=v_I-1 \)
Por lo tanto cualquier árbol H=\( (V,E) \) verifica \( \left |{E}\right |=\left |{V}\right |-1 \)
Por otro lado, sea G un bosque con p componentes conexas. Como cada componente es un árbol, se cumple
\( e_i=v_i-1, \forall{\, 1\leq{i\leq{p}}} \). Como las componentes son disjuntas,
\( \displaystyle\sum_{i=1}^p{}e_i=e_G \) y \( \displaystyle\sum_{i=1}^p{}v_i=v_G \), por lo tanto
\( e_G=v_G-p \)
Aunque todavia me falta probar (*)
Saludos,
