-1
$\begingroup$

If $G$ is an acyclic graph, then every subgraph of $G$ is acyclic.

Suggestions for this exercise.

$\endgroup$
2
  • 1
    $\begingroup$ It's obvious, if you think about what it says. $\endgroup$ – saulspatz Apr 11 at 0:09
  • 2
    $\begingroup$ Forget about graphs and cycles. Think for a moment. $\endgroup$ – bubba Apr 11 at 0:38
2
$\begingroup$

Suppose you had a cyclic sub-graph $G'$ of $G$. Then there would be some cycle in $G'$. This cycle would also be a cycle in $G$, contradicting the hypothesis that $G$ is acyclic.

$\endgroup$
2
$\begingroup$

Hint: if there were no elephants in England, then there would certainly not be any elephants in London, or Manchester, or any other English city. Generalize.

$\endgroup$

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