Expand acyclic graphs to acyclic graphs

35 Views Asked by At

I am learning about Kruskal Algorithm to find minimal spanning trees. To show that the spanning tree which is constructed with that Algorithm is minimal, I need to prove this statement:

Let $G=(V,E)$ be a graph, and let $G_1=(V,H)$ and $G_2=(V,K)$ be two acyclic subgraphs of $G$ such that $|H| < |K|$. Then, there exists $e\in K\setminus H$ such that $G'=(V,H\cup\{e\})$ is an acyclic subgraph of $G$.

This theorem is similar to the property of linear independent sets in vector spaces that allow us to expand any independent set to a basis.

I would thank to receive any hint to prove that statement.