Let F be a maximal forest of G. Show that: (a) For every component H of G, F ∩ H is a spanning tree of H

문제출처

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

Solution

1. A component $H$ of $G$ is a connected subgraph of $G$. Thus, $H$ is connected by definition. $F$ is a maximal forest of $G$, meaning that $F$ is an acyclic subgraph of $G$ and spans all components of $G$.

2. Since $F$ is a forest, it contains no cycles. Thus, $F \cap H$, as a subgraph of $F$, must also be acyclic.

3. $F$ is maximal. This means that it spans all vertices of $G$, including all the vertices in each component $H$. Thus, $F \cap H$ includes all vertices of $H$.

4. Since $H$ is a connected component and $F \cap H$ contains all vertices of $H$ and no cycles, $F \cap H$ must be connected. Otherwise, $F$ would not be maximal, contradicting the definition of $F$.

5. Since $F \cap H$ is acyclic, includes all vertices of $H$, and is connected, it must be a spanning tree of $H$.

• Therefore, for every component $H$, $F \cap H$ is a spanning tree of $H$.