0
$\begingroup$

I know that there must be one cycle.

But I want to make sure that every node is in some cycle.

My idea of proof: take the (largest) cycle, remove. Those nodes are ok.

I am left with a graph in which all nodes still have in- and out-degree 1. So I can keep doing the same all day until I finish.

Is there a hole in my argument or a counter-example?

Edit: Okay I was wrong! Have a graph with x,y,z being all connected, a-b being connected, and x pointing at e and e pointing at a. Doesn't work!

Is there any further restriction in the literature that could guarantee that this does not happen? I am aware of that one requiring all nodes having two out and in degree.

Improve this question
$\endgroup$
1
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W. ♦
    Commented Sep 15 at 1:31

1 Answer 1

Reset to default
1
$\begingroup$

Your proof is not correct. After removing the largest cycle, it is not necessarily true that all remaining nodes have in-degree and out-degree >=1. It is easy to construct a counter-example (I leave that to you).

Improve this answer
$\endgroup$
1
  • $\begingroup$ I constructed a counterexample indeed. $\endgroup$
    – fox
    Commented Sep 15 at 1:36

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.