Completion of acyclic sub graph

484 Views Asked by At

Statement: Given an acyclic subgraph of a connected graph, show that this subgraph can be completed into a spanning tree of the graph.

I know that there is a theorem that states that any connected graph has a spanning tree but I'm not sure if that is important or not. Im thinking that to prove the statement at the top, one would take a maximal acyclic subgraph (the spanning tree) and show that it must include any acyclic subgraph though I'm not entirely sure how to work out the details of that.

1

There are 1 best solutions below

0
On BEST ANSWER

Your intuition is pretty good. Let's call your graph $G$ and the acyclic subgraph $H$. Define the set of acyclic subgraphs of $G$ that contains $H$. In this set, take a subgraph with the biggest number of edges (let's call this graph $T$). Then, try to prove why $T$ has at most $|V(G)|-1$ edges (you need the hypothesis that $T$ is acyclic there), and why $T$ cannot have less than $|V(G)|-1$ edges (you need the hypothesis that $G$ is connected there). Once you proved these too, you know that $T$ is an acyclic subgraph of $G$ that has $|V(G)|-1$ edges, hence it's a spanning tree.

Note that you will need to use several times the fact that a tree on $n$ vertices has $n-1$ edges.