Let F be a maximal forest of G. Show that: $e(F) = n(G) − c(G)$, where e, n, and c are the number of edges, vertices, and compo-nents, respectively.

문제출처

광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 5

Solution

1. $G$ has $c(G)$ components. Each component $H$ of $G$ is connected and contains a spanning tree $F \cap H$, as shown in part (a).

2. A spanning tree with $k$ vertices has exactly $k-1$ edges, since a tree with $k$ vertices has $k-1$ edges by definition.

3. Therefore, for each component $H$, if $H$ has $n(H)$ vertices, the spanning tree $F \cap H$ has $n(H)-1$ edges.

4. Now, summing over all components of $G$, the total number of edges in the forest $F$ is the sum of $(n(H) - 1)$ over all components $H$:
$$e(F) = \sum_H (n(H) - 1).$$

5. Since the sum of the number of vertices in all components is the total number of vertices $n(G)$, and there are $c(G)$ components, this simplifies to:
$$e(F) = n(G) - c(G).$$