1
$\begingroup$

If there exists a directed graph with $n$ vertices and $n$ edges, where each vertex has exactly one outgoing edge, and there exists multiple cycles (>=2), is it possible to form a graph where all the cycles are connected in one component?

$\endgroup$

closed as off-topic by Henrik, Misha Lavrov, jvdhooft, Chris Custer, A. Goodier Apr 11 '18 at 8:14

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Henrik, Misha Lavrov, jvdhooft, Chris Custer, A. Goodier
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ A connected graph with $n$ vertices and $n-1$ edges is a tree. $\endgroup$ – saulspatz Apr 11 '18 at 5:31
  • $\begingroup$ Have you tried drawing such a graph to see if you can do it? $\endgroup$ – Misha Lavrov Apr 11 '18 at 6:19
  • $\begingroup$ @saulspatz notice it's $n$ edges and not $n-1$ edges $\endgroup$ – Simon Park Apr 11 '18 at 6:43
  • $\begingroup$ @Misha Lavrov I tried drawing many times but couldn't find an instance where two cycles could be in the same component, so I would like to believe it is not possible $\endgroup$ – Simon Park Apr 11 '18 at 6:44
  • $\begingroup$ @SimonPark Yes, you add one edge to a tree. How many cycle does that create? $\endgroup$ – saulspatz Apr 11 '18 at 14:44