Proving an acyclic subgraph of a connected graph can be completed into a spanning tree of the graph

Question

In my intro to combinatorics class, I am trying to prove that an acyclic subgraph of a connected graph can be completed into a spanning tree of the graph.

This is our first week into graph theory and in general I am having trouble with formal proofs in graph theory. Specifically, I have no idea if my proof is a proper formal proof and if it's needlessly overcomplicated.

I also saw this MathSE post Completion of acyclic sub graph but I tried going about it a different way than the hint given in the answers proposed.

This is one of the proofs I came up with:

$\underline{Proof}$

Let $G'=(V',E')$ be an acyclic subgraph of $G=(V,E)$ where $V'\subseteq V$ and $E'\subseteq E$. We know that $G'$ is a forest (a disjoint collection of trees) so we can partition the vertives of $V'$ into $V'_1, V'_2,\dots,V'_k$ for the $k$ components that make up $G'$.

Since $G$ is connected, then $\forall~i\in\{1,2,\dots,k\}~\exists~v_0\in V_i'$ where there exists a path to some $v_1\in V_j'$ for some $i\neq j$ such that the path $v_0v_2v_3v_4\dots v_mv_1$ where $v_2,v_3,\dots v_m\in V\setminus V'$ where $v_0v_2v_3v_4\dots v_mv_1$ is the shortest path from $v_0$ to $v_1$ (note the path could be just $v_0v_1$). We know this path does not contain any cycles otherwise it would not be the shortest path.

We will then connect these edges from the path s.t. $\{v_0,v_2\},\{v_2,v_3\},\dots\{v_{m-1},v_m\},\{v_m,v_1\}\in E'$. Doing this $\forall~V_i'$ will connect all the components of the subgraph $G'$. We can ensure that thsi will not introduce any cucles as we chose a $v_0$ that either

1.) Immediately connected to some $v_1$ (i.e. $\{v_0,v_1\}\in E$) or

2.) Connected to some $v_2\in V\setminus V'$ thus not creating a cycle with the points in that $V_i'$ and the rest of the $v_2,v_3,\dots,v_m$ form the smallest path and thus are acyclic too which immediately connect and terminate at some $v_1\in V_j'$.

Let $V'$ now also include all the vertices used to connect the $k$ components (and $E'$ include all the corresponding edges from the paths).

There still may be some points in $V\setminus V'$ which need to be connected. Since $G$ is connected, we know $\exists~v\in V\setminus V'$ s.t. $\exists~v'\in V'$ where $\{v,v'\}\in E$. We can add the certex $v$ to $V'$ and the edge $\{v,v'\}$ to $E'$ as this is just connecting an additional leaf. Doing this for all remaining $v\in V\setminus V'$ until there is non will result in a fully connected, acyclic graph $G'$. Thus $G'$ must have $n-1$ edges, therefore proving that $G'$ can be completed into a spanning tree of the graph $G$, as desired.

$\underline{End~Proof}$

I also highly considered starting with the graph $G$ and using the lemma that removing any edge of a cycle of a connected graph preserves connectedness. I would do that by starting with $G$ and removing any edge of a cycle as long as that edge isn't in $E'$ where $G'=(V',E')$ is the acyclic subgraph until there were no cycles remaining leaving me with a acyclic spanning graph containing $G'$ which is the spanning tree we want.

Thanks in advance for any advice.

Answer 1

Using a well known theorem proved in my class which states:

A connected graph on $n$ vertices with $n-1$ edges is a tree (cycle-free)

I fixed my proof as so, thanks to the advice of @dbal, @kabenyuk, and @MathieuRund.

Proof

Let $G'=(V,E')$ be an acyclic subgraph of $G=(V,E)$ where $E'\subseteq E$ and $|V|=n$. We know that $G'$ is a forest (a disjoint collection of trees) so we can partition the vertices of $V$ into $V_1, V_2,\dots,V_k$ for the $k$ components that make up $G'$ (some of these components may just be isolated points).

Note that this means $G'$ has $n-k$ edges since:

The $i$-th tree has $n_i$ vertices and $n_i - 1$ edges, for $i = 1, . . . , k$. Let $n$ be the total number of vertices, $\displaystyle{n = \sum_{i=1}^k n_i}$. The total number of edges is $\displaystyle{\sum_{i=1}^k (n_i-1)=\sum_{i=1}^k (n_i)-k=n-k}$, as desired.

Since $G$ is connected, then $\forall~i\in\{1,2,\dots,k\}~\exists~v_0\in V_i$ there exists some $v_1\in V_j$ where for some $i\neq j$ we have $\{v_0,v_1\}\in E$.

We can then add this edge to $E'$ and repeat this whole process.

Each repetition will decrease the number of components (including the number of $V_i$'s we are considering each iteration) by one. And to connect all $k$ components this will introduce $k-1$ edges leaving us with a connected graph on $n$ vertices with $n-k+k-1=n-1$ edges. From our Theorem in class, we know that a a connected graph on $n$ vertices with $n-1$ edges is cycle-free and thus a tree,

Therefore proving that $G'$ can be completed into a spanning tree of the graph $G$, as desired.

End Proof