0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.