0
$\begingroup$

Within a directed simple graph, are all vertices within a strongly connected component with 2 or more vertices part of a cycle?

$\endgroup$
3
  • $\begingroup$ What is simple connected component? Do you mean weakly or what? $\endgroup$
    – rus9384
    Oct 17, 2017 at 0:53
  • $\begingroup$ @rus9384 Good catch. Meant strongly connected component $\endgroup$
    – WHY
    Oct 17, 2017 at 4:09
  • $\begingroup$ All are part of the same cycle? (Trivially no). Or just all contained in some cycles? $\endgroup$
    – rus9384
    Oct 17, 2017 at 5:14

1 Answer 1

1
$\begingroup$

Suppose it's not the case, it means that there is a node $v$ that is either isolated (contradicts $n \geq 2$) or has an arrow that is incident to it. Let this arrow be from $v$ to $v'$, with no loss of generality. Since we have supposed that $v$ is not part of a cycle, it's impossible to go from $v'$ to $v$, which contradicts strong connectivity.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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