0
$\begingroup$

Prove that a maximal acylic subgraph of a graph $G$ consists of a spanning tree from each component of $G$.

My approach: to obtain a maximal acyclic subgraph of $G$ we can delete edges from cycles in the graph, while keeping components connected. In this way we obtain a tree in each component of $G$ and they are spanning because we kept the components connected.

Does this prove the statement? Thanks for any tips.

$\endgroup$
1
$\begingroup$

I believe your proof is valid. The only correction I'd make is that they are spanning not because we kept the components connected, but because we only removed edges (and not vertices) in order to obtain them (which is exactly the definition of "spanning"). They are trees because we destroyed every cycle while keeping the components connected. Finally, the subgraph we obtain is maximally acyclic, because any other subgraph that contains it has to have a cycle.

$\endgroup$
1
  • $\begingroup$ Makes sense. thank you! $\endgroup$ – mandella Nov 20 '17 at 16:59

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.